TCSLib

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

Definition 88.1 Radon-Nikodym density
✓
#

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.

Theorem 88.2 Nonnegativity of the Radon–Nikodym density
✓

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\).

Theorem 88.3 Measurability of the Radon–Nikodym density
✓

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.

Theorem 88.4 Integrability of the Radon–Nikodym density
✓

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 \).

Theorem 88.5 Integral of the Radon–Nikodym derivative equals one
✓

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 \):

\[ \int _{\Omega } \frac{d\mu }{d\nu }(x)\, d\nu (x) = 1. \]
Theorem 88.6 Integrability of the Radon–Nikodym density minus one
✓

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 \).

Theorem 88.7 Integrability of the deviation of the Radon–Nikodym density from one
✓

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 \).

Theorem 88.8 Mean of the Radon–Nikodym density minus one vanishes
✓

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

\[ \int _{\Omega } \left(\frac{d\mu }{d\nu }(x) - 1\right)\, d\nu (x) = 0. \]
Theorem 88.9 Set difference of two measures as an integral of the density minus one
✓

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

\[ \mu (S) - \nu (S) \; =\; \int _{S} \left( \frac{d\mu }{d\nu }(x) - 1 \right) d\nu (x). \]
Theorem 88.10 Positive part integrates to half the \(L^1\) norm at mean zero
✓

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:

\[ \int _{\{ x\, :\, g(x)\ge 0\} } g(x)\, d\mu \; =\; \tfrac {1}{2}\int _\Omega \left\lvert g(x)\right\rvert \, d\mu . \]
Theorem 88.11 Supremum of absolute set-integrals of a mean-zero function
✓

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:

\[ \sup _{S\text{ measurable}} \left\lvert *\right\rvert {\int _S g\, d\mu } \; =\; \int _{\{ x \, :\, g(x) \ge 0\} } g\, d\mu . \]
Definition 88.12 Density absolute integral
✓

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\).

Definition 88.13 Density positive set
✓

The density positive set is \(\{ x \in \Omega : \mathrm{rnDensity}(\mu ,\nu )(x) \ge 1\} \), the region where \(\mu \) locally dominates \(\nu \).

Theorem 88.14 Measurability of the density positive set
✓

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 \).

Definition 88.15 Density positive integral
✓

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

\[ \mathrm{TV}_{\sup }(\mu ,\nu ) = \sup \bigl\{ \, \left\lvert \mu (S) - \nu (S)\right\rvert : S \subseteq \Omega \text{ measurable}\, \bigr\} , \]

equals the excess mass of \(\mu \) over \(\nu \) on the region where \(\mu \) locally dominates:

\[ \mathrm{TV}_{\sup }(\mu ,\nu ) = \int _{\{ x\, :\, \frac{d\mu }{d\nu }(x)\, \ge \, 1\} } \left(\frac{d\mu }{d\nu }(x) - 1\right)\, d\nu (x). \]
Theorem 88.17 Total variation distance as an integral of density excess
✓

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 \):

\[ \tfrac {1}{2}\, \lVert \mu - \nu \rVert _{\mathrm{TV}} = \int _{\left\{ \, x \in \Omega \; :\; \frac{d\mu }{d\nu }(x) \ge 1\, \right\} } \left(\frac{d\mu }{d\nu }(x) - 1\right)\, d\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\):

\[ \int _{\{ x\, :\, \frac{d\mu }{d\nu }(x)\, \ge \, 1\} } \left(\frac{d\mu }{d\nu }(x)-1\right)\, d\nu (x) \; =\; \frac{1}{2}\int _{\Omega } \left|\frac{d\mu }{d\nu }(x)-1\right|\, d\nu (x). \]
Theorem 88.19 A Fenchel-type inequality for the Kullback–Leibler function
✓

For every real number \(u \ge 0\) and every real number \(y\),

\[ u\, y \; \le \; \left(u\ln u - u + 1\right) + e^{y} - 1, \]

where the term \(u\ln u\) is taken to be \(0\) at \(u = 0\).

Theorem 88.20 Exponential tilting by the cumulant generating function normalises to one
✓

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

\[ \int _\Omega e^{\, t X(x) - \Lambda (t)}\, d\mu (x) = 1. \]
Theorem 88.21 Integrability of the centred exponential moment
✓

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)}\).

Theorem 88.22 A variational inequality for the mean of a random variable
✓

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

\[ t \int _\Omega f(x)\, X(x)\, d\mu (x) \; \le \; \int _\Omega \bigl(f(x)\log f(x) - f(x) + 1\bigr)\, d\mu (x) + \Lambda (t). \]
Theorem 88.23 A Pinsker-type inequality for the Kullback–Leibler generator
✓

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

\[ \tfrac {1}{2}\Bigl(\int _\Omega \left\lvert f(x) - 1\right\rvert \, d\mu \Bigr)^{2} \; \le \; \int _\Omega \varphi (f(x))\, d\mu . \]
Theorem 88.24 Total variation distance via the density’s L¹-deviation from one
✓

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,

\[ \mathrm{TV}(\mu ,\nu ) = \frac{1}{2}\int _{\Omega } \left| \frac{d\mu }{d\nu }(x) - 1 \right| \, d\nu (x). \]
Theorem 88.25 A Pinsker-type inequality for the Radon–Nikodym density
✓

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

\[ \frac{1}{2}\left(\int _\Omega \left\lvert f(x) - 1\right\rvert \, d\nu (x)\right)^{2} \; \le \; \int _\Omega \bigl(f(x)\log f(x) - f(x) + 1\bigr)\, d\nu (x), \]

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\).

Theorem 88.26 Two integral forms of the Kullback–Leibler divergence
✓

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

\[ \int _\Omega \varphi \! \left(\frac{d\mu }{d\nu }(x)\right) d\nu (x) \; =\; \int _\Omega \log \frac{d\mu }{d\nu }(x)\, d\mu (x), \]

where \(\varphi (t) = t\log t + 1 - t\).

Theorem 88.27 Pinsker-type bound via the KL integral
✓

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

\[ \frac{1}{2}\left(\int _{\Omega } \left|\frac{d\mu }{d\nu }(x) - 1\right|\, d\nu (x)\right)^{2} \; \le \; \int _{\Omega } \log \frac{d\mu }{d\nu }(x)\, d\mu (x), \]

where the inner integral on the left is the \(L^{1}(\nu )\)-distance of the density from the constant \(1\).

Theorem 88.28 Pinsker’s inequality under absolute continuity
✓

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

\[ 2\, \mathrm{TV}(\mu ,\nu )^2 \; \le \; \int _\Omega \log \frac{d\mu }{d\nu }(x)\, d\mu (x), \]

the right-hand side being the Kullback–Leibler divergence of \(\mu \) from \(\nu \).

Theorem 88.29 Pinsker’s inequality under absolute continuity
✓

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 \} \),

\[ 2\, \mathrm{TV}(\mu ,\nu )^2 \; \le \; \mathrm{KL}(\mu \, \| \, \nu ), \]

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 \).

Theorem 88.30 Pinsker’s inequality under absolute continuity
✓

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

\[ 2\, \mathrm{TV}(\mu ,\nu )^2 \le D_{\mathrm{KL}}(\mu \, \| \, \nu ). \]
Theorem 88.31 Pinsker’s inequality
✓

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

\[ 2\, \mathrm{TV}(\mu ,\nu )^2 \; \le \; \mathrm{KL}(\mu \, \| \, \nu ), \]

where the left-hand side is regarded as an element of the extended nonnegative reals \([0,\infty ]\).

Theorem 88.32 Pinsker’s inequality for finite KL divergence
✓

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

\[ 2\, \mathrm{TV}(\mu ,\nu )^2 \; \le \; \mathrm{KL}(\mu \, \| \, \nu ). \]

88.3 Additional declarations

Theorem 88.33 Factorisation of the CGF-tilted exponential
✓
#

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}\).