Abstract: Let 0 <; ϵ <; 1/2 be a noise parameter, and let Tϵ be the noise operator acting on functions on the Boolean cube {0,1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> . Let f be a nonnegative function on {0,1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> . We upper bound the entropy of Tϵ f by the average entropy of conditional expectations of f, given sets of roughly (1-2ϵ) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n 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 ϵ. Then, setting v = (1-2ϵ) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> · n, we have (up to lower order terms): H(X⊕Z) ≥ n · H <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> (ϵ+ (1-2ϵ) · H <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">|B| = v</sub> H ({X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> } <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">iϵB</sub> }/v))). Assuming ϵ ≥ 1/2 - δ, for some absolute constant δ > 0, this inequality, combined with a strong version of a theorem of Friedgut et al., due to Jendrej et al., shows that if a Boolean function f is close to a characteristic function g of a subcube of dimension n-1, then the entropy of T <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ϵ</sub> f is at most that of Tϵg. Taken together with a recent result of Ordentlich et al., this shows that the most informative Boolean function conjecture of Courtade and Kumar holds for high noise ϵ ≥1/2 - δ. Namely, if X is uniformly distributed in {0,1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> and Y is obtained by flipping each coordinate of X independently with probability ϵ, then, provided ϵ ≥ 1/2 - δ, for any Boolean function f holds I (f(X);Y) ≤ 1 - H(ϵ).
Publication Year: 2016
Publication Date: 2016-10-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 29
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot