On the Most Informative Boolean Functions of the Very Noisy Channel
share
Let X^n be an independently identically distributed Bernoulli (1/2) random variables and let Y^n be the result of passing X^n through a binary symmetric channel (BSC) with crossover probability α. For any Boolean function f: {0,1}^n→{0,1}, Courtade and Kumar postulated that I(f(X^n);Y^n)< 1-H(α). In this paper, we prove, in a purely mathematical point of view, that the conjecture is true in high noise regime by showing that H(α)-H(f(X^n)|Y^n)<1-H(f(X^n)) holds for α∈[1/2-δ,1/2+δ], where δ>0 is some universally small constant. We first point out that in high noise regime, a function f is more informative if the second derivative of H(α)-H(f(X^n)|Y^n) has a larger value at α=1/2. Then we show that, the ratio spectrum of f^-1(0), an integer sequence which characterizes the structure of f^-1(0), is the fundamental metric that determines the second derivative of H(α)-H(f(X^n)|Y^n) evaluated at α=1/2. With |f^-1(0)| fixed, lex function is a locally most informative function for the very noisy BSC. The dictator function f(X^n)=X_i, (1< i< n), with i=1 being a special case of lex function |f^-1(0)|=2^n-1, is the globally most informative function for the very noisy BSC as it is the only type of functions that maximize the second derivative of H(α)-H(f(X^n)|Y^n) evaluated at α=1/2 to 0 over all possible |f^-1(0)|.
READ FULL TEXT