Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913707433394176 |
|---|---|
| author | Zhu, Xiaohan Ohannessian, Mesrob I. Srebro, Nathan |
| author_facet | Zhu, Xiaohan Ohannessian, Mesrob I. Srebro, Nathan |
| contents | We provide finite sample upper and lower bounds on the Binomial tail probability which are a direct application of Sanov's theorem. We then use these to obtain high probability upper and lower bounds on the minimum of i.i.d. Binomial random variables. Both bounds are finite sample, asymptotically tight, and expressed in terms of the KL-divergence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_18611 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence Zhu, Xiaohan Ohannessian, Mesrob I. Srebro, Nathan Probability Machine Learning We provide finite sample upper and lower bounds on the Binomial tail probability which are a direct application of Sanov's theorem. We then use these to obtain high probability upper and lower bounds on the minimum of i.i.d. Binomial random variables. Both bounds are finite sample, asymptotically tight, and expressed in terms of the KL-divergence. |
| title | Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence |
| topic | Probability Machine Learning |
| url | https://arxiv.org/abs/2502.18611 |