91 Communication Complexity — Pinsker

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

91.2 Declarations

Definition 91.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 91.2 Radon-Nikodym density is nonnegative

✓

For all \(x \in \Omega \), \(\mathrm{rnDensity}(\mu ,\nu )(x) \ge 0\).

Theorem 91.3 Radon-Nikodym density is measurable

✓

The function \(x \mapsto \mathrm{rnDensity}(\mu ,\nu )(x)\) is measurable.

Theorem 91.4 Radon-Nikodym density is \(\nu \)-integrable

✓

The function \(\mathrm{rnDensity}(\mu ,\nu )\) is integrable with respect to \(\nu \).

Theorem 91.5 Integral of density equals one under absolute continuity

✓

If \(\mu \ll \nu \), then \(\int \mathrm{rnDensity}(\mu ,\nu )(x)\, d\nu = 1\).

Theorem 91.6 \(\mathrm{rnDensity} - 1\) is integrable

✓

The function \(x \mapsto \mathrm{rnDensity}(\mu ,\nu )(x) - 1\) is integrable with respect to \(\nu \).

Theorem 91.7 \(|\mathrm{rnDensity} - 1|\) is integrable

✓

The function \(x \mapsto |\mathrm{rnDensity}(\mu ,\nu )(x) - 1|\) is integrable with respect to \(\nu \).

Theorem 91.8 Integral of \(\mathrm{rnDensity} - 1\) is zero under absolute continuity

✓

If \(\mu \ll \nu \), then \(\int (\mathrm{rnDensity}(\mu ,\nu )(x) - 1)\, d\nu = 0\).

Theorem 91.9 Measure difference as set integral of density shift

✓

If \(\mu \ll \nu \) and \(S \subseteq \Omega \) is measurable, then

\[ \mu (S) - \nu (S) \; =\; \int _S \bigl(\mathrm{rnDensity}(\mu ,\nu )(x) - 1\bigr)\, d\nu . \]

Theorem 91.10 Nonneg-part integral equals half the \(L^1\) norm when mean is zero

✓

Let \(\mu \) be a finite measure and \(g : \Omega \to \mathbb {R}\) measurable, integrable, and mean-zero (\(\int g\, d\mu = 0\)). Then

\[ \int _{\{ x\, :\, g(x)\ge 0\} } g(x)\, d\mu \; =\; \tfrac {1}{2}\int |g(x)|\, d\mu . \]

Theorem 91.11 Supremum of absolute set-integrals equals nonneg part when mean is zero

✓

Let \(\mu \) be a finite measure and \(g\) measurable, integrable, and mean-zero. Then

\[ \sup _{S\text{ measurable}}\Bigl|\int _S g\, d\mu \Bigr| \; =\; \int _{\{ g \ge 0\} } g\, d\mu . \]

Definition 91.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 91.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 91.14 Density positive set is measurable

✓

The density positive set \(\{ x : \mathrm{rnDensity}(\mu ,\nu )(x) \ge 1\} \) is a measurable subset of \(\Omega \).

Definition 91.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.

Theorem 91.16 TV distance supremum equals density positive integral under absolute continuity

✓

If \(\mu \ll \nu \), then \(\mathrm{tvDistanceSup}(\mu ,\nu ) = \mathrm{densityPositiveIntegral}(\mu ,\nu )\).

Theorem 91.17 TV distance equals density positive integral under absolute continuity

✓

If \(\mu \ll \nu \), then \(\mathrm{TV}(\mu ,\nu ) = \mathrm{densityPositiveIntegral}(\mu ,\nu )\).

Theorem 91.18 Density positive integral equals half the density absolute integral

✓

If \(\mu \ll \nu \), then \(\mathrm{densityPositiveIntegral}(\mu ,\nu ) = \tfrac {1}{2}\, \mathrm{densityAbsIntegral}(\mu ,\nu )\).

Theorem 91.19 Pointwise KL inequality: \(u y \le \mathrm{klFun}(u) + e^y - 1\)

✓

For real numbers \(u \ge 0\) and \(y\), one has \(u \cdot y \le \mathrm{klFun}(u) + e^y - 1\), where \(\mathrm{klFun}(u) = u \ln u - u + 1\).

Theorem 91.20 Integral of \(e^{tX - \Lambda (t)}\) equals one

✓

Let \(\mu \) be a probability measure, \(X : \Omega \to \mathbb {R}\) and \(t \in \mathbb {R}\). If \(e^{tX}\) is \(\mu \)-integrable, then \(\int e^{t X(x) - \Lambda _\mu (t)}\, d\mu = 1\), where \(\Lambda _\mu (t) = \log \int e^{tX}\, d\mu \) is the cumulant generating function.

Theorem 91.21 \(e^{tX - \Lambda (t)}\) is integrable

✓

If \(e^{tX}\) is \(\mu \)-integrable, then so is \(x \mapsto e^{t X(x) - \Lambda _\mu (t)}\).

Theorem 91.22 Variational bound: \(t \int f X\, d\mu \le \int \mathrm{klFun}(f)\, d\mu + \Lambda _\mu (t)\)

✓

Let \(f, X : \Omega \to \mathbb {R}\) with \(f \ge 0\) and \(\int f\, d\mu = 1\). Under suitable integrability conditions on \(f\), \(X\), and \(e^{tX}\),

\[ t \int f(x)\, X(x)\, d\mu \; \le \; \int \mathrm{klFun}(f(x))\, d\mu + \Lambda _\mu (t). \]

Theorem 91.23 \(\tfrac {1}{2}(\int |f-1|)^2 \le \int \mathrm{klFun}(f)\)

✓

Let \(f : \Omega \to \mathbb {R}\) with \(f \ge 0\), \(\int f\, d\mu = 1\), \(f\) integrable, and \(\mathrm{klFun}(f)\) integrable. Then

\[ \tfrac {1}{2}\Bigl(\int |f(x) - 1|\, d\mu \Bigr)^2 \; \le \; \int \mathrm{klFun}(f(x))\, d\mu . \]

Theorem 91.24 TV distance equals half density absolute integral under absolute continuity

✓

If \(\mu \ll \nu \), then \(\mathrm{TV}(\mu ,\nu ) = \tfrac {1}{2}\, \mathrm{densityAbsIntegral}(\mu ,\nu )\).

Theorem 91.25 \(\tfrac {1}{2}(\mathrm{densityAbsIntegral})^2 \le \int \mathrm{klFun}(\mathrm{rnDensity})\)

✓

If \(\mu \ll \nu \) and the log-likelihood ratio \(\mathrm{llr}(\mu ,\nu )\) is \(\mu \)-integrable, then

\[ \tfrac {1}{2}\, \mathrm{densityAbsIntegral}(\mu ,\nu )^2 \; \le \; \int \mathrm{klFun}\bigl(\mathrm{rnDensity}(\mu ,\nu )(x)\bigr)\, d\nu . \]

Theorem 91.26 KL-function integral equals log-likelihood integral

✓

If \(\mu \ll \nu \) and \(\mathrm{llr}(\mu ,\nu )\) is \(\mu \)-integrable, then

\[ \int \mathrm{klFun}\bigl(\mathrm{rnDensity}(\mu ,\nu )(x)\bigr)\, d\nu \; =\; \int \mathrm{llr}(\mu ,\nu )(x)\, d\mu . \]

Theorem 91.27 Density \(L^1\) Pinsker bound via KL integral

✓

If \(\mu \ll \nu \) and \(\mathrm{llr}(\mu ,\nu )\) is \(\mu \)-integrable, then

\[ \tfrac {1}{2}\, \mathrm{densityAbsIntegral}(\mu ,\nu )^2 \; \le \; \int \mathrm{llr}(\mu ,\nu )(x)\, d\mu . \]

Theorem 91.28 Real Pinsker inequality under absolute continuity and integrability

✓

If \(\mu \ll \nu \) and \(\mathrm{llr}(\mu ,\nu )\) is \(\mu \)-integrable, then

\[ 2\, \mathrm{TV}(\mu ,\nu )^2 \; \le \; \int \mathrm{llr}(\mu ,\nu )(x)\, d\mu . \]

Theorem 91.29 Pinsker inequality (\(\mathbb {R}_{\ge 0}^\infty \) form) under absolute continuity and integrability

✓

If \(\mu \ll \nu \) and \(\mathrm{llr}(\mu ,\nu )\) is \(\mu \)-integrable, then

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

in \(\mathbb {R}_{\ge 0}^\infty \).

Theorem 91.30 Pinsker inequality under absolute continuity

✓

If \(\mu \ll \nu \) (without any integrability assumption), then \(\mathrm{ofReal}(2\, \mathrm{TV}(\mu ,\nu )^2) \le \mathrm{KL}(\mu \| \nu )\) in \(\mathbb {R}_{\ge 0}^\infty \).

Theorem 91.31 Pinsker’s inequality

✓

For any two probability measures \(\mu \) and \(\nu \) on \(\Omega \),

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

where the inequality is in \(\mathbb {R}_{\ge 0}^\infty \) and KL divergence uses natural logarithms.

Theorem 91.32 Real-valued Pinsker corollary for finite KL divergence

✓

If \(\mathrm{KL}(\mu \| \nu ) \ne \infty \), then

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

providing a real-valued form of Pinsker’s inequality convenient when finiteness of the KL divergence is already known.