87 Communication Complexity — Entropy
87.1 Overview
This module collects entropy and mutual-information lemmas needed for the Newman theorem development. It establishes upper bounds on (Shannon) entropy in terms of alphabet size, monotonicity and data-processing inequalities for mutual information and conditional mutual information, chain rules, and stability results under almost-sure equality and identical distributions.
87.2 Declarations
If the alphabet type \(S\) has \(\mathrm{card}(S) \le N\), then for any random variable \(X : \Omega \to S\) and measure \(\mu \),
If \(\mathrm{card}(S) \le 2^c\) for some \(c : \mathbb {N}\), then
For measurable \(X\) and \(Y\) under a zero-or-probability measure \(\mu \) with finite ranges,
For measurable \(X\) and \(Y\) under a zero-or-probability measure \(\mu \) with finite ranges,
If \(X =^{\mu \text{-a.e.}} X'\) and \(Y =^{\mu \text{-a.e.}} Y'\), then \(I[X : Y;\mu ] = I[X' : Y';\mu ]\).
If \(f : T \to V\) is measurable and injective, then \(I[X : f \circ Y;\mu ] = I[X : Y;\mu ]\).
If \(X =^{\mu \text{-a.e.}} c\) for some constant \(c : S\), then \(I[X : Y;\mu ] = 0\).
If \(Y =^{\mu \text{-a.e.}} c\) for some constant \(c : T\), then \(I[X : Y;\mu ] = 0\).
If \(X =^{\mu \text{-a.e.}} c\) for some constant \(c : S\), then \(I[X : Y \mid Z;\mu ] = 0\).
If \(Y =^{\mu \text{-a.e.}} c\) for some constant \(c : T\), then \(I[X : Y \mid Z;\mu ] = 0\).
For measurable \(X : \Omega \to S\) and \(Y : \Omega \to T\) with finite \(S\) and \(T\), if
holds for all \(x, y\), then \(X\) and \(Y\) are independent under \(\mu \).
For measurable \(X\), \(Y\), \(Z\) under a zero-or-probability measure with finite ranges,
For measurable \(X\), \(Y\), \(Z\) under a zero-or-probability measure with finite ranges,
For measurable \(X\), \(Y\), \(Z\) under a zero-or-probability measure with finite ranges,
For measurable \(X\), \(Y\), \(Z\) under a zero-or-probability measure with finite ranges,
If \(f : U \to S \to V\) is any function (where \(Z : \Omega \to U\) is the conditioning variable), then applying \(f(Z(\omega ))\) to \(X(\omega )\) before measuring mutual information cannot increase it:
For a measurable function \(f : U \to T \to V\) (with \(Z : \Omega \to U\) the conditioning variable), applying \(f(Z(\omega ))\) to \(Y(\omega )\) cannot increase conditional mutual information:
Adding a deterministic function of the conditioning variable to the conditioning variable does not change conditional mutual information:
For a measurable \(f : U \to S \to V\), conditioning additionally on a deterministic function of \(X\) and \(Z\) cannot increase conditional mutual information:
For a measurable \(f : U \to T \to V\), conditioning additionally on a deterministic function of \(Y\) and \(Z\) cannot increase conditional mutual information:
Let \(W : \Omega \to V\) and \(f : V \to U\). If \(I[X : W \mid f \circ W;\mu ] = 0\) (i.e., the coarse variable \(f \circ W\) carries all the information about \(X\) that \(W\) does), then
For measurable \(X\), \(W\), \(Y\), \(Z\) with finite ranges under a zero-or-probability measure,
For measurable \(X\), \(Y\), \(W\), \(Z\) with finite ranges under a zero-or-probability measure,
For measurable \(X\), \(Y\), \(W\), \(Z\) with finite ranges under a probability measure,
For a boolean-vector-valued random variable \(X : \Omega \to (\mathrm{Fin}\, m \to \mathrm{Bool})\) and an index \(i : \mathrm{Fin}\, m\), the strict prefix \(\mathrm{boolVectorStrictPrefix}\, X\, i\, \omega \) is the restriction of \(X(\omega )\) to coordinates \(0, 1, \ldots , i-1\).
For a boolean-vector-valued \(X : \Omega \to (\mathrm{Fin}\, m \to \mathrm{Bool})\),
where \(X_i(\omega ) = X(\omega )(i)\).
For a finite measure \(\mu \) and measurable sets \(F \subseteq A\),
For a finite measure \(\mu \) and measurable sets \(F \subseteq A\),
If the conditioning variable is a pair \((K, Z)\) with \(K\) taking values in a finite type \(A\), then
Let \(A = Z^{-1}(B)\) for some measurable \(B\). Then, under a probability measure \(\mu \),
For measurable \(X\), \(Y\), \(W\) with finite ranges under a zero-or-probability measure,
If \(I[X : W \mid Y;\mu ] \le I[X : W;\mu ]\), then
Under a probability measure, if \(X =^{\mu \text{-a.e.}} X'\) and \(Y =^{\mu \text{-a.e.}} Y'\) (with all four variables measurable and of finite range), then \(H[X \mid Y;\mu ] = H[X' \mid Y';\mu ]\).
Under a probability measure, if \(X =^{\mu \text{-a.e.}} X'\) and \(Y =^{\mu \text{-a.e.}} Y'\), then \(I[X : Y \mid Z;\mu ] = I[X' : Y' \mid Z;\mu ]\) (the conditioning variable \(Z\) is unchanged).
Under a probability measure, if \(X =^{\mu \text{-a.e.}} X'\), \(Y =^{\mu \text{-a.e.}} Y'\), and \(Z =^{\mu \text{-a.e.}} Z'\), then \(I[X : Y \mid Z;\mu ] = I[X' : Y' \mid Z';\mu ]\).
Version of ProbabilityTheory.condMutualInfo_congr_ae for finite measurable sample spaces: measurability and finite-range conditions are inferred automatically from the CommunicationComplexity.FiniteMeasureSpace and Finite instances, so only the a.e. equality hypotheses need to be supplied.
If \((X, Y, Z)\) and \((X', Y', Z')\) have the same joint distribution (i.e., are identically distributed), then \(I[X : Y \mid Z;\mu ] = I[X' : Y' \mid Z';\mu ']\).
Finite-space version of ProbabilityTheory.IdentDistrib.condMutualInfo_eq: measurability and finite-range conditions are inferred from CommunicationComplexity.FiniteMeasureSpace and Finite instances.
If \(f : T \to V\) and \(g : U \to W\) are measurable injections, then
If \((X, Y)\) and \((X', Y')\) have the same joint law and \(s \subseteq B\) is measurable, then \(X\) under \(\mu [\, |\, Y^{-1}(s)]\) and \(X'\) under \(\mu '[\, |\, Y'^{-1}(s)]\) are identically distributed.