{
  "id": "math/0412377",
  "version": "v1",
  "published": "2004-12-19T07:14:57.000Z",
  "updated": "2004-12-19T07:14:57.000Z",
  "title": "Noise Stability of Weighted Majority",
  "authors": [
    "Yuval Peres"
  ],
  "comment": "six pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-12-19T07:14:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05"
    ],
    "keywords": [
      "noise stability",
      "upper bound",
      "weighted majority functions",
      "weighted majority changes",
      "probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math.....12377P"
    }
  }
}