The maximum mutual information between the output of a discrete symmetric channel and several classes of Boolean functions of its input

Abstract

We prove the Courtade-Kumar conjecture, for several classes of n-dimensional Boolean functions, for all $n\ge 2$ and for all values of the error probability of the binary symmetric channel, $0\le p\le 1/2$. This conjecture states that the mutual information between any Boolean function of an n-dimensional vector of independent and identically distributed inputs to a memoryless binary symmetric channel and the corresponding vector of outputs is upper-bounded by $1-H(p)$, where $H(p)$ represents the binary entropy function. That is, let $\mathbf{X}=[X_1\dots X_n]$ be a vector of independent and identically distributed Bernoulli(1/2) random variables, which are the input to a memoryless binary symmetric channel, with the error probability in the interval $0\le p\le 1/2$ and $\mathbf{Y}=[Y_1\dots Y_n]$ the corresponding output. Let $f:\{0,1{\}}^n\to \{0,1\}$ be an n-dimensional Boolean function. Then, $\mathrm{MI}(f(X),Y)\le 1-H(p)$. Our proof employs Karamata's theorem, concepts from probability theory, transformations of random variables and vectors and algebraic manipulations.

Withdrawn due to rejection by the IEEE Transactions on Information Theory; the reason for rejection was limited originality and scope of the proposed result

References in corpus (1)

• Mutual information in random Boolean models of regulatory networks