Remarks on the Most Informative Function Conjecture at fixed mean

Abstract

In 2013, Courtade and Kumar posed the following problem: Let $\mathbf{x}\sim \{\pm 1{\}}^n$ be uniformly random, and form $\mathbf{y}\sim \{\pm 1{\}}^n$ by negating each bit of $\mathbf{x}$ independently with probability $\alpha$. Is it true that the mutual information $I(f(\mathbf{x});\mathbf{y})$ is maximized among $f:\{\pm 1{\}}^n\to \{\pm 1\}$ by $f(x)=x_1$? We do not resolve this problem. Instead, we make a couple of observations about the fixed-mean version of the conjecture. We show that Courtade and Kumar's stronger Lex Conjecture fails for small noise rates. We also prove a continuous version of the conjecture on the sphere and show that it implies the previously-known analogue for Gaussian space.

Cited by in corpus (3)

• An Isoperimetric Result on High-Dimensional Spheres
• Principal Inertia Components and Applications
• On the $\Phi$-Stability and Related Conjectures