# Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence

arXiv: https://arxiv.org/abs/2502.18611 · HTML: https://mlsanity.com/paper/2502.18611/

## 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.

## Built on by (most cited first, 3 of 3)

- [Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification](https://mlsanity.com/paper/2503.02110/) (2025)
- [Learning to Choose or Choosing to Learn: Best-of-N vs. Supervised Fine-Tuning for Bit String Generation](https://mlsanity.com/paper/2505.17288/) (2025)
- [Overfitting and Generalizing with (PAC) Bayesian Prediction in Noisy Binary Classification](https://mlsanity.com/paper/2603.22644/) (2026)

## 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.