[Back]

G. Pichler, P. Piantanida, G. Matz:
"Dictator Functions Maximize Mutual Information";
Annals of Applied Probability, 28 (2018), 5.

Let (Xⁿ,Yⁿ) denote n independent, identically distributed copies of two arbitrarily correlated Rademacher random variables (X,Y). We prove that the inequality I(f(Xⁿ); g(Yⁿ)) ≤ I(X;Y) holds for any two Boolean functions: f,g: {-1,1}ⁿ → {-1,1} (I(·;·) denotes mutual information). We further show that equality in general is achieved only by the dictator functions f(xⁿ) = ±g(xⁿ) = ±xᵢ, i ∈ {1,2,...,n}.

Boolean functions, mutual information, Fourier analysis, binary sequences, binary codes

http://dx.doi.org/10.1214/18-AAP1384