TCSLib

87 Communication Complexity — KL Divergence

87.1 Overview

This module develops concrete sum formulas for the Kullback–Leibler divergence on finite measurable spaces, bridging Mathlib’s InformationTheory.klDiv with the PFR real-valued KLDiv entropy API. The main results give explicit pointwise summation formulas for KL divergence between finite measures and PMFs, and show how they specialize to the Boolean (\(\mathrm{Bool}\)) case.

87.2 Declarations

Theorem 87.1 KL divergence as a log-likelihood-ratio sum (absolutely continuous case)
✓

Let \(\Omega \) be a finite measurable space, and let \(\mu \) and \(\nu \) be finite measures on \(\Omega \) with \(\mu \) absolutely continuous with respect to \(\nu \). Write \(\tfrac {d\mu }{d\nu }\) for the Radon–Nikodym derivative and let \(\mathrm{llr}(\omega ) = \log \tfrac {d\mu }{d\nu }(\omega )\) be the log-likelihood ratio at \(\omega \). Then the Kullback–Leibler divergence satisfies

\[ D_{\mathrm{KL}}(\mu \, \| \, \nu ) = \left[\; \sum _{\omega \in \Omega } \mu (\{ \omega \} )\, \mathrm{llr}(\omega ) \; +\; \nu (\Omega ) \; -\; \mu (\Omega ) \; \right]_{+}, \]

where \([\, x\, ]_{+}\) denotes the value in \([0,\infty ]\) obtained by viewing the real number \(x\) as a nonnegative extended real, negative values being sent to \(0\).

Theorem 87.2 KL divergence on a finite space as a log-likelihood-ratio sum
✓

Let \(\Omega \) be a finite discrete measurable space, and let \(\mu \) and \(\nu \) be finite measures on \(\Omega \). If there is a point \(\omega \in \Omega \) with \(\nu (\{ \omega \} ) = 0\) but \(\mu (\{ \omega \} ) \neq 0\), then the Kullback–Leibler divergence is infinite, \(D_{\mathrm{KL}}(\mu \, \| \, \nu ) = \infty \). Otherwise,

\[ D_{\mathrm{KL}}(\mu \, \| \, \nu ) = \left(\ \sum _{\omega \in \Omega } \mu (\{ \omega \} )\, \log \frac{d\mu }{d\nu }(\omega )\ + \nu (\Omega )\ -\ \mu (\Omega )\ \right)_{\! +}, \]

where \(\log \frac{d\mu }{d\nu }\) denotes the log-likelihood ratio of \(\mu \) with respect to \(\nu \), the measures are read as their real values, and \((x)_+\) takes the enclosed real number as a nonnegative extended real, sending any negative value to \(0\).

Theorem 87.3 KL divergence of probability mass functions
✓

Let \(\Omega \) be a finite discrete measurable space, and let \(p\) and \(q\) be probability mass functions on \(\Omega \). Then the Kullback–Leibler divergence between the probability measures they induce is

\[ D_{\mathrm{KL}}(p \, \| \, q) = \begin{cases} \infty & \text{if } q(\omega ) = 0 \text{ and } p(\omega ) \neq 0 \text{ for some } \omega \in \Omega , \\[4pt] \displaystyle \sum _{\omega \in \Omega } p(\omega )\, \log \! \frac{p(\omega )}{q(\omega )} & \text{otherwise,} \end{cases} \]

where in the second case the (nonnegative) real sum is read as an element of \([0,\infty ]\).

Theorem 87.4 Radon–Nikodym derivative as a ratio of point masses
✓

Let \(\Omega \) be a finite measurable space carrying two finite measures \(\mu \) and \(\nu \) with \(\mu \ll \nu \), and let \(\omega \in \Omega \) be a point whose singleton has positive mass, \(\nu (\{ \omega \} ) \neq 0\). Then the Radon–Nikodym derivative of \(\mu \) with respect to \(\nu \) takes at \(\omega \) the value

\[ \frac{d\mu }{d\nu }(\omega ) = \frac{\mu (\{ \omega \} )}{\nu (\{ \omega \} )}, \]

where both sides are read as nonnegative real numbers.

Theorem 87.5 Singleton mass times log-likelihood ratio
✓

Let \(\Omega \) be a finite discrete measurable space, let \(\mu \) and \(\nu \) be finite measures on \(\Omega \) with \(\mu \) absolutely continuous with respect to \(\nu \), and let \(\omega \in \Omega \). Writing \(\mu (\{ \omega \} )\) and \(\nu (\{ \omega \} )\) for the (real-valued) masses of the singleton \(\{ \omega \} \) and \(\log \frac{d\mu }{d\nu }\) for the log-likelihood ratio of \(\mu \) against \(\nu \), one has

\[ \mu (\{ \omega \} ) \cdot \log \frac{d\mu }{d\nu }(\omega ) = \mu (\{ \omega \} ) \cdot \log \! \left(\frac{\mu (\{ \omega \} )}{\nu (\{ \omega \} )}\right). \]
Theorem 87.6 KL divergence on a finite space as a sum of log-ratios
✓

Let \(\Omega \) be a finite discrete measurable space, and let \(\mu \) and \(\nu \) be finite measures on \(\Omega \). If there is a point \(\omega \in \Omega \) with \(\nu (\{ \omega \} ) = 0\) but \(\mu (\{ \omega \} ) \neq 0\), then the Kullback–Leibler divergence is infinite:

\[ D_{\mathrm{KL}}(\mu \, \| \, \nu ) = \infty . \]

Otherwise,

\[ D_{\mathrm{KL}}(\mu \, \| \, \nu ) = \left( \sum _{\omega \in \Omega } \mu (\{ \omega \} ) \, \log \! \frac{\mu (\{ \omega \} )}{\nu (\{ \omega \} )} + \nu (\Omega ) - \mu (\Omega ) \right)_{+}, \]

where each \(\mu (\{ \omega \} )\), \(\nu (\{ \omega \} )\), \(\mu (\Omega )\), \(\nu (\Omega )\) denotes the (real-valued) mass of the indicated set and \((x)_{+} = \max (x, 0)\) is the nonnegative part.

Theorem 87.7 Finiteness of KL divergence against a full-support measure
✓

Let \(\Omega \) be a finite discrete measurable space, and let \(\mu \) and \(\nu \) be probability measures on \(\Omega \). If \(\nu \) assigns positive mass to every point, meaning \(\nu (\{ \omega \} ) \neq 0\) for all \(\omega \in \Omega \), then the Kullback–Leibler divergence \(D_{\mathrm{KL}}(\mu \, \| \, \nu )\) is finite.

Theorem 87.8 Kullback–Leibler divergence between probability mass functions
✓

Let \(\Omega \) be a finite discrete measurable space, and let \(p\) and \(q\) be probability mass functions on \(\Omega \), each regarded as the probability measure it induces. Then the Kullback–Leibler divergence \(D_{\mathrm{KL}}(p \, \| \, q)\), valued in \([0,\infty ]\), equals \(+\infty \) whenever there exists some \(\omega \in \Omega \) with \(q(\omega ) = 0\) and \(p(\omega ) \neq 0\), and otherwise equals the value in \([0,\infty ]\) obtained from

\[ \sum _{\omega \in \Omega } p(\omega )\, \log \! \frac{p(\omega )}{q(\omega )}, \]

where each mass \(p(\omega )\), \(q(\omega )\) is taken as its real value and negative sums are read as \(0\).

Theorem 87.9 Real-valued and extended KL divergence agree on Bool
✓

Let \(\mu \) and \(\nu \) be probability measures on the two-point space \(\mathrm{Bool} = \{ \mathrm{false}, \mathrm{true}\} \), and suppose \(\nu \) has full support, meaning \(\nu (\{ b\} ) \gt 0\) for each of the two points \(b\). Writing \(D_{\mathrm{KL}}(\mu \, \| \, \nu ) \in [0, \infty ]\) for the Kullback–Leibler divergence valued in the extended nonnegative reals, its real cast agrees with the real-valued Kullback–Leibler divergence of the identity map, regarded as a random variable, under \(\mu \) and under \(\nu \); that is,

\[ \bigl(D_{\mathrm{KL}}(\mu \, \| \, \nu )\bigr)_{\mathbb {R}} = \mathrm{KL}[\, \mathrm{id};\mu \, \# \, \mathrm{id};\nu \, ]. \]
Theorem 87.10 Real value of a conditioned Boolean Kullback–Leibler divergence
✓

Let \(\mu \) be a finite measure on a measurable space \(\Omega \), let \(X:\Omega \to \{ 0,1\} \) be a measurable Boolean random variable, and let \(S\subseteq \Omega \) be a set whose \(\mu \)-measure (as a real number) is nonzero, so that the conditional probability measure \(\mu (\cdot \mid S)\) is well defined. Let \(\nu \) be a probability measure on \(\{ 0,1\} \) that assigns strictly positive mass to each of the two points. Then the extended-real Kullback–Leibler divergence of the law \(X_{\ast }\, \mu (\cdot \mid S)\) of \(X\) under the conditional measure relative to \(\nu \), taken as a real number, coincides with its explicit pointwise value:

\[ D_{\mathrm{KL}}\! \bigl(X_{\ast }\, \mu (\cdot \mid S)\ \big\| \ \nu \bigr) = \sum _{b\in \{ 0,1\} } \mathbb {P}_{\mu (\cdot \mid S)}(X=b)\, \log \frac{\mathbb {P}_{\mu (\cdot \mid S)}(X=b)}{\nu (\{ b\} )}. \]