{
  "id": "2210.16100",
  "version": "v1",
  "published": "2022-10-28T12:49:32.000Z",
  "updated": "2022-10-28T12:49:32.000Z",
  "title": "An OSSS-type inequality for uniformly drawn subsets of fixed size",
  "authors": [
    "Jacob van den Berg"
  ],
  "comment": "23 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "The OSSS inequality [O'Donnell, Saks, Schramm and Servedio, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), Pittsburgh (2005)] gives an upper bound for the variance of a function f of independent 0-1 valued random variables, in terms of the influences of these random variables and the computational complexity of a (randomised) algorithm for determining the value of f. Duminil-Copin, Raoufi and Tassion [Annals of Mathematics 189, 75-99 (2019)] obtained a generalization to monotonic measures and used it to prove new results for Potts models and random-cluster models. Their generalization of the OSSS inequality raises the question if there are still other measures for which a version of that inequality holds. We derive a version of the OSSS inequality for a family of measures that are far from monotonic, namely the k-out-of-n measures (these measures correspond with drawing k elements from a set of size n uniformly). We illustrate the inequality by studying the event that there is an occupied horizontal crossing of an R times R box on the triangular lattice in the site percolation model where exactly half of the vertices in the box are occupied.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-10-28T12:49:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "60C05"
    ],
    "keywords": [
      "uniformly drawn subsets",
      "osss-type inequality",
      "fixed size",
      "random variables",
      "46th annual ieee symposium"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}