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
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
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\).
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,
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\).
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
where in the second case the (nonnegative) real sum is read as an element of \([0,\infty ]\).
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
where both sides are read as nonnegative real numbers.
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
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:
Otherwise,
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.
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.
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
where each mass \(p(\omega )\), \(q(\omega )\) is taken as its real value and negative sums are read as \(0\).
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,
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: