Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence
This work provides theoretical tools for probability and statistics, particularly in analyzing extreme values of Binomial distributions, but it is incremental as it builds on existing methods like Sanov's theorem.
The paper derived finite sample upper and lower bounds for the Binomial tail probability using Sanov's theorem, and applied these to bound the minimum of i.i.d. Binomial random variables, with both bounds being asymptotically tight and expressed in terms of KL-divergence.
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.