Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 0 of its 4 references that are in the map. First posted on arXiv 25 Feb 2025.
Builds on
0 of 4 references.
No references here yet.
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.
- 2025Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classificationcited by 2
- 2025Learning to Choose or Choosing to Learn: Best-of-N vs. Supervised Fine-Tuning for Bit String Generationcited by 0
- 2026Overfitting and Generalizing with (PAC) Bayesian Prediction in Noisy Binary Classificationcited by 0
- 2026Overfitting and Generalizing with (PAC) Bayesian Prediction in Noisy Binary Classification23 Mar 2026
- 2025Learning to Choose or Choosing to Learn: Best-of-N vs. Supervised Fine-Tuning for Bit String Generation22 May 2025
- 2025Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification3 Mar 2025