TCSLib

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

Theorem 87.1 Entropy bounded by log of alphabet size
#

If the alphabet type \(S\) has \(\mathrm{card}(S) \le N\), then for any random variable \(X : \Omega \to S\) and measure \(\mu \),

\[ H[X;\mu ] \; \le \; \log N. \]
Theorem 87.2 Entropy bounded by \(c \log 2\) when alphabet fits in \(c\) bits

If \(\mathrm{card}(S) \le 2^c\) for some \(c : \mathbb {N}\), then

\[ H[X;\mu ] \; \le \; c \cdot \log 2. \]
Theorem 87.3 Mutual information bounded by left entropy
#

For measurable \(X\) and \(Y\) under a zero-or-probability measure \(\mu \) with finite ranges,

\[ I[X : Y;\mu ] \; \le \; H[X;\mu ]. \]
Theorem 87.4 Mutual information bounded by right entropy

For measurable \(X\) and \(Y\) under a zero-or-probability measure \(\mu \) with finite ranges,

\[ I[X : Y;\mu ] \; \le \; H[Y;\mu ]. \]
Theorem 87.5 Mutual information invariant under a.e. substitution
#

If \(X =^{\mu \text{-a.e.}} X'\) and \(Y =^{\mu \text{-a.e.}} Y'\), then \(I[X : Y;\mu ] = I[X' : Y';\mu ]\).

Theorem 87.6 Mutual information invariant under injective recoding of right variable

If \(f : T \to V\) is measurable and injective, then \(I[X : f \circ Y;\mu ] = I[X : Y;\mu ]\).

Theorem 87.7 Mutual information zero when left variable is a.e. constant

If \(X =^{\mu \text{-a.e.}} c\) for some constant \(c : S\), then \(I[X : Y;\mu ] = 0\).

Theorem 87.8 Mutual information zero when right variable is a.e. constant

If \(Y =^{\mu \text{-a.e.}} c\) for some constant \(c : T\), then \(I[X : Y;\mu ] = 0\).

Theorem 87.9 Conditional mutual information zero when left variable is a.e. constant

If \(X =^{\mu \text{-a.e.}} c\) for some constant \(c : S\), then \(I[X : Y \mid Z;\mu ] = 0\).

Theorem 87.10 Conditional mutual information zero when right variable is a.e. constant

If \(Y =^{\mu \text{-a.e.}} c\) for some constant \(c : T\), then \(I[X : Y \mid Z;\mu ] = 0\).

Theorem 87.11 Independence from singleton-fiber factorization

For measurable \(X : \Omega \to S\) and \(Y : \Omega \to T\) with finite \(S\) and \(T\), if

\[ \mu (X^{-1}\{ x\} \cap Y^{-1}\{ y\} ) = \mu (X^{-1}\{ x\} )\cdot \mu (Y^{-1}\{ y\} ) \]

holds for all \(x, y\), then \(X\) and \(Y\) are independent under \(\mu \).

Theorem 87.12 Conditional mutual information bounded by left conditional entropy

For measurable \(X\), \(Y\), \(Z\) under a zero-or-probability measure with finite ranges,

\[ I[X : Y \mid Z;\mu ] \; \le \; H[X \mid Z;\mu ]. \]
Theorem 87.13 Conditional mutual information bounded by right conditional entropy

For measurable \(X\), \(Y\), \(Z\) under a zero-or-probability measure with finite ranges,

\[ I[X : Y \mid Z;\mu ] \; \le \; H[Y \mid Z;\mu ]. \]
Theorem 87.14 Conditional mutual information bounded by left entropy

For measurable \(X\), \(Y\), \(Z\) under a zero-or-probability measure with finite ranges,

\[ I[X : Y \mid Z;\mu ] \; \le \; H[X;\mu ]. \]
Theorem 87.15 Conditional mutual information bounded by right entropy

For measurable \(X\), \(Y\), \(Z\) under a zero-or-probability measure with finite ranges,

\[ I[X : Y \mid Z;\mu ] \; \le \; H[Y;\mu ]. \]
Theorem 87.16 Conditional data processing: postprocessing depending on conditioning value

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:

\[ I[\omega \mapsto f(Z(\omega ))(X(\omega )) : Y \mid Z;\mu ] \; \le \; I[X : Y \mid Z;\mu ]. \]
Theorem 87.17 Conditional data processing on the right depending on conditioning value

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:

\[ I[X : \omega \mapsto f(Z(\omega ))(Y(\omega )) \mid Z;\mu ] \; \le \; I[X : Y \mid Z;\mu ]. \]
Theorem 87.18 Conditioning on \((Z, f(Z))\) equals conditioning on \(Z\)

Adding a deterministic function of the conditioning variable to the conditioning variable does not change conditional mutual information:

\[ I[X : Y \mid (\omega \mapsto (Z(\omega ),\, f(Z(\omega ))));\mu ] \; =\; I[X : Y \mid Z;\mu ]. \]
Theorem 87.19 Extra left-side conditioning cannot increase 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:

\[ I[X : Y \mid (\omega \mapsto (Z(\omega ),\, f(Z(\omega ))(X(\omega ))));\mu ] \; \le \; I[X : Y \mid Z;\mu ]. \]
Theorem 87.20 Extra right-side conditioning 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:

\[ I[X : Y \mid (\omega \mapsto (Z(\omega ),\, f(Z(\omega ))(Y(\omega ))));\mu ] \; \le \; I[X : Y \mid Z;\mu ]. \]
Theorem 87.21 Finer conditioning increases conditional mutual information when coarse carries no extra info

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

\[ I[X : Y \mid f \circ W;\mu ] \; \le \; I[X : Y \mid W;\mu ]. \]
Theorem 87.22 Chain rule: splitting a left-side pair

For measurable \(X\), \(W\), \(Y\), \(Z\) with finite ranges under a zero-or-probability measure,

\[ I[(X,W) : Y \mid Z;\mu ] \; =\; I[X : Y \mid Z;\mu ] \; +\; I[W : Y \mid (X, Z);\mu ]. \]
Theorem 87.23 Chain rule: splitting a right-side pair

For measurable \(X\), \(Y\), \(W\), \(Z\) with finite ranges under a zero-or-probability measure,

\[ I[X : (Y, W) \mid Z;\mu ] \; =\; I[X : Y \mid Z;\mu ] \; +\; I[X : W \mid (Y, Z);\mu ]. \]
Theorem 87.24 Pairing the right variable cannot decrease conditional mutual information

For measurable \(X\), \(Y\), \(W\), \(Z\) with finite ranges under a probability measure,

\[ I[X : W \mid Z;\mu ] \; \le \; I[X : (Y, W) \mid Z;\mu ]. \]
Definition 87.25 Strict prefix of a boolean vector
#

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

Theorem 87.26 Chain rule for conditional mutual information against a boolean vector

For a boolean-vector-valued \(X : \Omega \to (\mathrm{Fin}\, m \to \mathrm{Bool})\),

\[ I[X : Y \mid Z;\mu ] \; =\; \sum _{i=0}^{m-1} I[X_i : Y \mid (\mathrm{boolVectorStrictPrefix}\, X\, i,\, Z);\mu ], \]

where \(X_i(\omega ) = X(\omega )(i)\).

Theorem 87.27 Iterated conditioning on a subset

For a finite measure \(\mu \) and measurable sets \(F \subseteq A\),

\[ (\mu [\, |\, A])[\, |\, F] \; =\; \mu [\, |\, F]. \]
Theorem 87.28 Real-mass reweighting for nested conditioning events

For a finite measure \(\mu \) and measurable sets \(F \subseteq A\),

\[ \mu _{\mathbb {R}}(A) \cdot (\mu [\, |\, A])_{\mathbb {R}}(F) \; =\; \mu _{\mathbb {R}}(F). \]
Theorem 87.29 Conditional mutual information as an average over a finite partition

If the conditioning variable is a pair \((K, Z)\) with \(K\) taking values in a finite type \(A\), then

\[ I[X : Y \mid (K, Z);\mu ] \; =\; \sum _{k : A} \mu _{\mathbb {R}}(K^{-1}\{ k\} ) \cdot I[X : Y \mid Z;\, \mu [\, |\, K \leftarrow k]]. \]
Theorem 87.30 Conditional mutual information on an event is bounded by the unconditional value

Let \(A = Z^{-1}(B)\) for some measurable \(B\). Then, under a probability measure \(\mu \),

\[ \mu _{\mathbb {R}}(A) \cdot I[X : Y \mid Z;\, \mu [\, |\, A]] \; \le \; I[X : Y \mid Z;\, \mu ]. \]
Theorem 87.31 Chain rule for mutual information: splitting a right-side pair

For measurable \(X\), \(Y\), \(W\) with finite ranges under a zero-or-probability measure,

\[ I[X : (Y, W);\mu ] \; =\; I[X : Y;\mu ] \; +\; I[X : W \mid Y;\mu ]. \]
Theorem 87.32 Conditional mutual information bounded by unconditioned mutual information

If \(I[X : W \mid Y;\mu ] \le I[X : W;\mu ]\), then

\[ I[X : Y \mid W;\mu ] \; \le \; I[X : Y;\mu ]. \]
Theorem 87.33 Conditional entropy invariant under a.e. substitution
#

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

Theorem 87.34 Conditional mutual information invariant under a.e. substitution of both variables

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

Theorem 87.35 Conditional mutual information invariant under a.e. substitution of all three variables

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

Theorem 87.36 Finite-space a.e. congruence for conditional mutual information

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.

Theorem 87.37 Conditional mutual information determined by the joint law

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

Theorem 87.38 Finite-space version: conditional mutual information determined by the joint law

Finite-space version of ProbabilityTheory.IdentDistrib.condMutualInfo_eq: measurability and finite-range conditions are inferred from CommunicationComplexity.FiniteMeasureSpace and Finite instances.

Theorem 87.39 Conditional mutual information invariant under injective recodings of right and conditioning variables

If \(f : T \to V\) and \(g : U \to W\) are measurable injections, then

\[ I[X : f \circ Y \mid g \circ Z;\mu ] \; =\; I[X : Y \mid Z;\mu ]. \]
Theorem 87.40 Identical distribution of pairs preserved under conditioning on the same set
#

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.