Noise Stability of Weighted Majority

Abstract

Benjamini, Kalai and Schramm (2001) showed that weighted majority functions of $n$ independent unbiased bits are uniformly stable under noise: when each bit is flipped with probability $\epsilon$, the probability $p_{\epsilon }$ that the weighted majority changes is at most $C{\epsilon }^{1/4}$. They asked what is the best possible exponent that could replace 1/4. We prove that the answer is 1/2. The upper bound obtained for $p_{\epsilon }$ is within a factor of $\sqrt{\pi /2}+o(1)$ from the known lower bound when $\epsilon \to 0$ and $n\epsilon \to \infty$.

six pages