Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.19541 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911893955805184 |
|---|---|
| author | Cerf, Raphaël |
| author_facet | Cerf, Raphaël |
| contents | We define the pivotal set of a Boolean function and we prove a fundamental inequality on its expected size, when the inputs are independent random coins of parameter~$p$. We give two complete proofs of this inequality. Along the way, we obtain the classical Margulis--Russo formula. We give a short proof of the classical Hoeffding inequality for i.i.d. Bernoulli random variables, and we use it to derive more complex deviations inequalities associated to the pivotal set. We follow finally Talagrand's footsteps and we discuss a beautiful inequality that he proved in the uniform case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19541 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The pivotal set of a Boolean function Cerf, Raphaël Probability We define the pivotal set of a Boolean function and we prove a fundamental inequality on its expected size, when the inputs are independent random coins of parameter~$p$. We give two complete proofs of this inequality. Along the way, we obtain the classical Margulis--Russo formula. We give a short proof of the classical Hoeffding inequality for i.i.d. Bernoulli random variables, and we use it to derive more complex deviations inequalities associated to the pivotal set. We follow finally Talagrand's footsteps and we discuss a beautiful inequality that he proved in the uniform case. |
| title | The pivotal set of a Boolean function |
| topic | Probability |
| url | https://arxiv.org/abs/2405.19541 |