Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2210.16100 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916292216225792 |
|---|---|
| author | Berg, Jacob van den Don, Henk |
| author_facet | Berg, Jacob van den Don, Henk |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_16100 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An OSSS-type inequality for uniformly drawn subsets of fixed size Berg, Jacob van den Don, Henk Probability 60K35 (Primary) 60C05 (Secondary) 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. |
| title | An OSSS-type inequality for uniformly drawn subsets of fixed size |
| topic | Probability 60K35 (Primary) 60C05 (Secondary) |
| url | https://arxiv.org/abs/2210.16100 |