Noise Stability of Weighted Majority
| dc.creator | Peres, Yuval | |
| dc.date | 2004-12-19 | |
| dc.date.accessioned | 2026-07-07T05:15:27Z | |
| dc.date.available | 2026-07-07T05:15:27Z | |
| dc.description | 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 $ε$, the probability $p_ε$ that the weighted majority changes is at most $Cε^{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_ε$ is within a factor of $\sqrt{π/2}+o(1)$ from the known lower bound when $ε\to 0$ and $nε\to \infty$. | |
| dc.description | six pages | |
| dc.identifier | https://arxiv.org/abs/math/0412377 | |
| dc.identifier | http://arxiv.org/abs/math/0412377 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/73633 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 60C05 | |
| dc.title | Noise Stability of Weighted Majority | |
| dc.type | text |