On the Entropy of a Noisy Function

DOI10.1109/TIT.2016.2584625zbMATH Open1359.94359arXiv1508.01464OpenAlexW2963653371MaRDI QIDQ2976554FDOQ2976554

Authors: Alex Samorodnitsky 

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Let $0<epsilon<1/2$ be a noise parameter, and let $T_{epsilon}$ be the noise operator acting on functions on the boolean cube ${0,1}^n$. Let $f$ be a nonnegative function on ${0,1}^n$. We upper bound the entropy of $T_{epsilon}f$ by the average entropy of conditional expectations of $f$, given sets of roughly $(1-2epsilon{)}^{2}cdotn$ variables. In information-theoretic terms, we prove the following strengthening of "Mrs. Gerber's lemma": Let $X$ be a random binary vector of length $n$, and let $Z$ be a noise vector, corresponding to a binary symmetric channel with crossover probability $epsilon$. Then, setting $v=(1-2epsilon{)}^{2}cdotn$, we have (up to lower-order terms): ${\displaystyle }$ HBig(X oplus ZBig) ge n cdot Hleft(epsilon ~+~ (1-2epsilon) cdot H^{-1}left(frac{{mathbb E}_{|B| = v} HBig({X_i}_{iin B}Big)}{v} ight) ight) ${\displaystyle }$ As an application, we show that for a boolean function $f$, which is close to a characteristic function $g$ of a subcube of dimension $n-1$, the entropy of $T_{epsilon}f$ is at most that of $T_{epsilon}g$. This, combined with a recent result of Ordentlich, Shayevitz, and Weinstein shows that the "Most informative boolean function" conjecture of Courtade and Kumar holds for high noise $epsilonge1/2-delta$, for some absolute constant $delta>0$. Namely, if $X$ is uniformly distributed in ${0,1}^n$ and $Y$ is obtained by flipping each coordinate of $X$ independently with probability $epsilon$, then, provided $epsilonge1/2-delta$, for any boolean function $f$ holds $IBig(f(X);YBig)le1-H(epsilon)$.

Full work available at URL: https://arxiv.org/abs/1508.01464

Mathematics Subject Classification ID

Measures of information, entropy (94A17)

Cited In (4)

• A structure theorem for almost low-degree functions on the slice
• Common Information, Noise Stability, and Their Extensions
• Comparison of contraction coefficients for \(f\)-divergences
• On the \(\Phi \)-stability and related conjectures

This page was built for publication: On the Entropy of a Noisy Function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976554)