Noise Stability of Weighted Majority

Details Noise Stability of Weighted Majority Noise Stability of Weighted Majority

2004-12-19

arxiv.org/abs/math/0412377v1

Mathematics

Probability

six pages

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

Noise Stability of Weighted Majority does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Noise Stability of Weighted Majority, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Noise Stability of Weighted Majority will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-16893