88 Communication Complexity — Pinsker
88.1 Overview
This module develops a self-contained proof of Pinsker’s inequality, which bounds the total variation distance between two probability measures by their KL divergence. The argument proceeds via the Radon-Nikodym density and a variational characterisation of total variation, culminating in \(2 \cdot \mathrm{TV}(\mu ,\nu )^2 \le \mathrm{KL}(\mu \| \nu )\).
88.2 Declarations
For two probability measures \(\mu \) and \(\nu \) on a measurable space \(\Omega \), the Radon-Nikodym density \(\mathrm{rnDensity}(\mu ,\nu )(x) \in \mathbb {R}\) is the real part of the Radon-Nikodym derivative \(\frac{d\mu }{d\nu }(x)\), obtained by converting the extended non-negative real value \(\mu .\mathrm{rnDeriv}\, \nu \, x\) to a real number via ENNReal.toReal.
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \). Then at every point \(x \in \Omega \), the real-valued Radon–Nikodym density \(\frac{d\mu }{d\nu }(x)\) satisfies \(\frac{d\mu }{d\nu }(x) \ge 0\).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and consider the real-valued Radon–Nikodym density \(x \mapsto \left(\tfrac {d\mu }{d\nu }(x)\right)\), obtained from the \([0,\infty ]\)-valued Radon–Nikodym derivative \(\tfrac {d\mu }{d\nu }\colon \Omega \to [0,\infty ]\) by taking its real value at each point. Then this function \(\Omega \to \mathbb {R}\) is measurable.
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(f\colon \Omega \to \mathbb {R}\) be the real-valued Radon–Nikodym density of \(\mu \) with respect to \(\nu \), that is, the function whose value at each point \(x\) is the real number obtained from the Radon–Nikodym derivative \(\frac{d\mu }{d\nu }(x)\). Then \(f\) is integrable with respect to \(\nu \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and suppose that \(\mu \) is absolutely continuous with respect to \(\nu \), written \(\mu \ll \nu \). Then the Radon–Nikodym derivative \(\frac{d\mu }{d\nu }\) integrates to one against \(\nu \):
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\frac{d\mu }{d\nu }\colon \Omega \to \mathbb {R}\) denote the real-valued Radon–Nikodym density of \(\mu \) with respect to \(\nu \). Then the function \(x \mapsto \frac{d\mu }{d\nu }(x) - 1\) is integrable with respect to \(\nu \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\frac{d\mu }{d\nu } : \Omega \to \mathbb {R}\) be the real-valued Radon–Nikodym density of \(\mu \) with respect to \(\nu \) (the extended nonnegative Radon–Nikodym derivative converted to a real number). Then the function \(x \mapsto \left\lvert \frac{d\mu }{d\nu }(x) - 1\right\rvert \) is integrable with respect to \(\nu \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and suppose that \(\mu \) is absolutely continuous with respect to \(\nu \). Writing \(\frac{d\mu }{d\nu }\) for the Radon–Nikodym density of \(\mu \) with respect to \(\nu \) (the real-valued version of the Radon–Nikodym derivative), one has
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \) with \(\mu \) absolutely continuous with respect to \(\nu \) (that is, \(\mu \ll \nu \)), and let \(S \subseteq \Omega \). Writing \(\frac{d\mu }{d\nu }\) for the (real-valued) Radon–Nikodym derivative of \(\mu \) with respect to \(\nu \), one has
Let \(\mu \) be a finite measure on a measurable space \(\Omega \), and let \(g : \Omega \to \mathbb {R}\) be measurable and integrable with mean zero, \(\int _\Omega g\, d\mu = 0\). Then the integral of \(g\) over the region where it is nonnegative equals half its \(L^1\) norm:
Let \(\mu \) be a finite measure on a measurable space \(\Omega \), and let \(g \colon \Omega \to \mathbb {R}\) be measurable and integrable with mean zero, \(\int _\Omega g\, d\mu = 0\). Then the supremum of \(\left\lvert \int _S g\, d\mu \right\rvert \) taken over all measurable sets \(S \subseteq \Omega \) equals the integral of \(g\) over the region where it is nonnegative:
The quantity \(\mathrm{densityAbsIntegral}(\mu ,\nu ) := \int |\mathrm{rnDensity}(\mu ,\nu )(x) - 1|\, d\nu \) is the \(L^1(\nu )\)-distance of the Radon-Nikodym density from \(1\).
The density positive set is \(\{ x \in \Omega : \mathrm{rnDensity}(\mu ,\nu )(x) \ge 1\} \), the region where \(\mu \) locally dominates \(\nu \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and for each \(x \in \Omega \) let \(\frac{d\mu }{d\nu }(x) \in \mathbb {R}\) denote the Radon–Nikodym derivative of \(\mu \) with respect to \(\nu \), taken as a real number. Then the set \(\left\{ x \in \Omega : \frac{d\mu }{d\nu }(x) \ge 1\right\} \), on which \(\mu \) locally dominates \(\nu \), is a measurable subset of \(\Omega \).
The density positive integral is \(\mathrm{densityPositiveIntegral}(\mu ,\nu ) := \int _{\mathrm{densityPositiveSet}} (\mathrm{rnDensity}(\mu ,\nu )(x)-1)\, d\nu \), the excess mass of \(\mu \) over \(\nu \) on the region where \(\mu \) dominates.
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and suppose \(\mu \) is absolutely continuous with respect to \(\nu \). Write \(\frac{d\mu }{d\nu }\) for the Radon–Nikodym derivative of \(\mu \) with respect to \(\nu \). Then the total variation distance, taken as the supremum
equals the excess mass of \(\mu \) over \(\nu \) on the region where \(\mu \) locally dominates:
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and suppose that \(\mu \) is absolutely continuous with respect to \(\nu \). Write \(\frac{d\mu }{d\nu }\) for the (real-valued) Radon–Nikodym derivative of \(\mu \) with respect to \(\nu \). Then the total variation distance between \(\mu \) and \(\nu \) equals the excess mass of \(\mu \) over \(\nu \) on the region where \(\mu \) locally dominates \(\nu \):
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), with \(\mu \) absolutely continuous with respect to \(\nu \), and write \(\frac{d\mu }{d\nu }\) for the Radon–Nikodym density of \(\mu \) with respect to \(\nu \). Then the excess mass of the density above \(1\), integrated over the region where the density is at least \(1\), equals half the \(L^1(\nu )\)-distance of the density from \(1\):
For every real number \(u \ge 0\) and every real number \(y\),
where the term \(u\ln u\) is taken to be \(0\) at \(u = 0\).
Let \(\mu \) be a probability measure on a measurable space \(\Omega \), let \(X : \Omega \to \mathbb {R}\) be a random variable, and let \(t \in \mathbb {R}\). Write \(\Lambda (t) = \log \int _\Omega e^{t X(x)}\, d\mu (x)\) for the cumulant generating function of \(X\) at \(t\). If the function \(x \mapsto e^{t X(x)}\) is \(\mu \)-integrable, then
Let \((\Omega ,\mu )\) be a measure space, let \(X\colon \Omega \to \mathbb {R}\) be a measurable function, and let \(t\in \mathbb {R}\). Write \(\Lambda (t)\) for the cumulant generating function of \(X\) under \(\mu \), that is, the logarithm of the moment generating function evaluated at \(t\). If the function \(x\mapsto e^{t\, X(x)}\) is \(\mu \)-integrable, then so is the function \(x\mapsto e^{t\, X(x)-\Lambda (t)}\).
Let \(\mu \) be a probability measure on a measurable space \(\Omega \), let \(f, X : \Omega \to \mathbb {R}\), and let \(t \in \mathbb {R}\). Suppose that \(f \ge 0\) pointwise, that \(\int _\Omega f\, d\mu = 1\), and that \(f\), the map \(x \mapsto f(x)\log f(x) - f(x) + 1\), the map \(x \mapsto e^{tX(x)}\), and the product \(fX\) are all \(\mu \)-integrable. Writing \(\Lambda (t) = \log \int _\Omega e^{tX}\, d\mu \) for the cumulant generating function of \(X\) under \(\mu \), one has
Let \((\Omega , \mu )\) be a probability space, and let \(\varphi (t) = t \log t - t + 1\) for \(t \ge 0\) denote the convex generator of the Kullback–Leibler divergence. Let \(f : \Omega \to \mathbb {R}\) be a measurable, integrable, nonnegative function with \(\int _\Omega f \, d\mu = 1\), so that \(f\) is the density of a probability measure with respect to \(\mu \), and assume that \(x \mapsto \varphi (f(x))\) is integrable with respect to \(\mu \). Then
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and suppose that \(\mu \) is absolutely continuous with respect to \(\nu \). Then the total variation distance between \(\mu \) and \(\nu \) equals one half of the density absolute integral, that is,
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \) with \(\mu \) absolutely continuous with respect to \(\nu \), and write \(f = \frac{d\mu }{d\nu }\) for the (real-valued) Radon–Nikodym density. Suppose the log-likelihood ratio \(x \mapsto \log \frac{d\mu }{d\nu }(x)\) is \(\mu \)-integrable. Then
where the left-hand inner integral is the \(L^1(\nu )\)-distance of the density from \(1\) and the right-hand integrand is the Kullback–Leibler integrand \(t \mapsto t\log t - t + 1\).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \) with \(\mu \) absolutely continuous with respect to \(\nu \), and write \(\frac{d\mu }{d\nu }\) for the (real-valued) Radon–Nikodym density of \(\mu \) with respect to \(\nu \). Assume that the log-likelihood ratio \(x \mapsto \log \frac{d\mu }{d\nu }(x)\) is \(\mu \)-integrable. Then
where \(\varphi (t) = t\log t + 1 - t\).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \) with \(\mu \) absolutely continuous with respect to \(\nu \), and write \(\frac{d\mu }{d\nu }\) for the (real-valued) Radon–Nikodym density. Suppose the log-likelihood ratio \(x \mapsto \log \frac{d\mu }{d\nu }(x)\) is \(\mu \)-integrable. Then
where the inner integral on the left is the \(L^{1}(\nu )\)-distance of the density from the constant \(1\).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and write \(\mathrm{TV}(\mu ,\nu )\) for their total variation distance. Suppose \(\mu \) is absolutely continuous with respect to \(\nu \), and that the log-likelihood ratio \(x \mapsto \log \frac{d\mu }{d\nu }(x)\) is \(\mu \)-integrable. Then
the right-hand side being the Kullback–Leibler divergence of \(\mu \) from \(\nu \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and suppose \(\mu \) is absolutely continuous with respect to \(\nu \) and that the log-likelihood ratio \(\log \frac{d\mu }{d\nu }\) is \(\mu \)-integrable. Then, as an inequality in the extended nonnegative reals \(\mathbb {R}_{\ge 0} \cup \{ \infty \} \),
where \(\mathrm{TV}(\mu ,\nu )\) is the total variation distance between \(\mu \) and \(\nu \) and \(\mathrm{KL}(\mu \, \| \, \nu )\) is the Kullback–Leibler divergence of \(\mu \) from \(\nu \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and suppose that \(\mu \) is absolutely continuous with respect to \(\nu \). Then the total variation distance \(\mathrm{TV}(\mu ,\nu )\) and the Kullback–Leibler divergence \(D_{\mathrm{KL}}(\mu \, \| \, \nu )\) (both taking values in \([0,\infty ]\)) satisfy
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\mathrm{TV}(\mu ,\nu )\) denote their total variation distance and \(\mathrm{KL}(\mu \, \| \, \nu )\) their Kullback–Leibler divergence. Then
where the left-hand side is regarded as an element of the extended nonnegative reals \([0,\infty ]\).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and suppose that the Kullback–Leibler divergence \(\mathrm{KL}(\mu \, \| \, \nu )\) is finite. Then the total variation distance \(\mathrm{TV}(\mu ,\nu ) = \tfrac {1}{2}\| \mu - \nu \| _{\mathrm{TV}}\) satisfies
88.3 Additional declarations
Let \(\mu \) be a measure on a measurable space \(\Omega \), let \(X\colon \Omega \to \mathbb {R}\), and let \(t \in \mathbb {R}\). Writing \(\Lambda (t)\) for the cumulant generating function of \(X\) under \(\mu \) at \(t\), the functions \(x \mapsto e^{\, t X(x) - \Lambda (t)}\) and \(x \mapsto e^{-\Lambda (t)} \cdot e^{\, t X(x)}\) are equal, i.e. the tilted exponential factors as the constant \(e^{-\Lambda (t)}\) times \(e^{\, tX}\).