Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence
Xiaohan Zhu, Mesrob I. Ohannessian, Nathan Srebro · 2025
Read Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence by Xiaohan Zhu, Mesrob I. Ohannessian, Nathan Srebro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-18611.txt.
Introduction
Xiaohan Zhu, Mesrob Ohannessian, and Nathan Srebro give tight bounds on binomial tail chances, in this 2025 paper. Such tails govern how low a set of coin-like trials can run. Their bounds flow directly from a classic large-deviation result.
The team then turn the bounds on a fresh question: the smallest value among many matched binomial draws. Both upper and lower bounds hold for finite samples, not just in the limit. Each is written through a standard divergence measure between distributions. The bounds grow exact as samples grow. The authors frame the work as clean, ready-to-use probability tools.
Catalog record
| CREATOR | Xiaohan Zhu, Mesrob I. Ohannessian, Nathan Srebro |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 10 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-18611
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence
Xiaohan Zhu, Mesrob I. Ohannessian, Nathan Srebro
Abstract
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.
The purpose of this note is to provide, in a self-contained and concise way, both upper
and
lower bounds on the Binomial tail, and through that, on the minimum of i.i.d. Binomial random variables. The upper bound on the minimum of i.i.d. Binomials can be seen as a special case of known uniform concentration guarantees. Our main purpose here, beyond providing an explicit, simple, and self-contained presentation, is to provide also simple matching
lower
bounds. Such lower bounds can then be used in constructing and analyzing lower bounds for different learning methods and situations.
We first prove a finite sample bound on the Binomial cumulative distribution function (CDF) by using Sanov’s theorem. Throughout, all logarithms are base-
2
and KL divergence is measured in bits.
Lemma 1
(Binomial tail).
Let
X\sim\frac{1}{n}\textnormal{Bin}(n,p)
be a scaled Binomial random variable. Then for
a\leq p
,
\log\mathbb{P}(X\leq a)\in-n\textsf{KL}(a\|p)\pm\left(4\log(n+1)+\left[\log\frac{p}{1-p}\right]_{+}\right),
where
\textsf{KL}(\alpha\|\beta)
denotes
\textsf{KL}(Ber(\alpha)\|Ber(\beta))=\alpha\log\frac{\alpha}{\beta}+(1-\alpha)\log\frac{1-\alpha}{1-\beta}
.
Proof:
We write
X=\frac{1}{n}\sum_{i=1}^{n}X_{i}
, where
X_{i}\overset{\mathrm{iid}}{\sim}\textnormal{Ber}(p)
, and so
X_{1},X_{2},\cdots,X_{n}
is a sequence of
n
symbols from the alphabet
\mathcal{X}=\{0,1\}
with type
(1-X,X)
. Denote the true distribution
Q=\textnormal{Ber}(p)
.
The upper bound follows directly from Sanov’s theorem
(
Cover and Thomas 2006
)
:
\log\mathbb{P}(X\leq a)\leq-n\textsf{KL}(a\|p)+2\log(n+1).
(1)
To get a finite sample lower bound, we round
a
to a multiple of
1/n
. That is, let
k=\lfloor an\rfloor
and
\tilde{a}=k/n
, so that
a-1/n<\tilde{a}\leq a
.
Let
\mathcal{P}_{n}=\{(P(0),P(1)):(\frac{0}{n},\frac{n}{n}),(\frac{1}{n},\frac{n-1}{n}),\cdots,(\frac{n}{n},\frac{0}{n})\}
be the set of types with denominator
n
, and
E=\{P:P(1)\leq a\}
. Then the type
P_{\tilde{a}}=(1-\tilde{a},\tilde{a})
lies in the intersection
E\cap\mathcal{P}_{n}
.
Given the type
P\in\mathcal{P}_{n}
, let
T(P)=\{x\in\mathcal{X}^{n}:P_{x}=P\}
denote the type class of
P
, which is the set of sequences of length
n
and and type
P
. Then, by adapting equations (11.104) to (11.106) in the lower bound proof of
Cover and Thomas 2006
, we have:
\begin{split}\mathbb{P}(X\leq a)=Q^{n}(E)&=\sum_{P\in E\cap\mathcal{P}_{n}}Q^{n}\left(T\left(P\right)\right)\\
&\geq Q^{n}\left(T\left(P_{\tilde{a}}\right)\right)\\
&\geq\frac{1}{(n+1)^{2}}2^{-n\textsf{KL}(\tilde{a}\|p)}.\end{split}
Taking the logarithm on both sides yields:
\log\mathbb{P}(X\leq a)\geq-2\log(n+1)-n\textsf{KL}(\tilde{a}\|p).
(*)
Since
a-\tilde{a}<1/n
,
H(a)-H(\tilde{a})<H(\frac{1}{n})<\frac{2}{n}\log n
. This implies that
\textsf{KL}(\tilde{a}\|p)-\textsf{KL}(a\|p)=(a-\tilde{a})\log\frac{p}{1-p}+H(a)-H(\tilde{a})\leq\frac{1}{n}\left[\log\frac{p}{1-p}\right]_{+}+\frac{2}{n}\log n
. Plugging this in the inequality (
*
‣
Proof:
) yields
\displaystyle\log\mathbb{P}(X\leq a)
\displaystyle\geq-2\log(n+1)-n\textsf{KL}(\tilde{a}\|p)
\displaystyle\geq-2\log(n+1)-\left(n\textsf{KL}(a\|p)+2\log n+\left[\log\frac{p}{1-p}\right]_{+}\right)
\displaystyle\geq-n\textsf{KL}(a\|p)-4\log(n+1)-\left[\log\frac{p}{1-p}\right]_{+}.
(2)
The upper bound (
1
) and lower bound (
2
) together yield the desired result.
Next, we use the finite sample bound on the Binomial CDF to prove the following concentration bounds of the minimum of i.i.d Binomials in terms of KL divergence.
Theorem 1
(minimum of i.i.d Binomial).
Let
\{X_{i}\}_{i=1}^{r}\overset{\mathrm{iid}}{\sim}\frac{1}{n}\textnormal{Bin}(n,p)
,
Z=\min_{i=1,\cdots,r}X_{i}
. Given fixed confidence parameter
\delta\in(0,1)
, let
\Delta(\delta,p,n)=\log\frac{1}{\delta/2}+4\log(n+1)+\left[\log\frac{p}{1-p}\right]_{+}
. If
\Delta(\delta,p,n)<\log r
, then with probability
1-\delta
, we have
Z<p\text{, and }\textsf{KL}(Z\|p)\in\frac{\log r\pm\Delta(\delta,p,n)}{n},
except that if
\textsf{KL}(0\|p)<\frac{\log r-\Delta(\delta,p,n)}{n}
, then with probability
1-\delta
,
Z=0
.
Proof:
Consider any interval
[a,b]
, such that
a\leq b<p
. Define the following events:
\displaystyle U
\displaystyle=
\displaystyle\{\textsf{KL}(Z\|p)\leq\textsf{KL}(a\|p)\},
\displaystyle L
\displaystyle=
\displaystyle\{\textsf{KL}(Z\|p)\geq\textsf{KL}(b\|p)\},
\displaystyle A
\displaystyle=
\displaystyle\{Z\geq a\},\textrm{ and}
\displaystyle B
\displaystyle=
\displaystyle\{Z\leq b\}.
a
b
p
B
A
U
L
By the monotonicity of the KL divergence, we have that
B\subseteq L
and
A\cap B\subseteq U
(but note that we generally
don’t
have
A\subseteq U
). This means that
A\cap B\subseteq U\cap L
, and consequently:
\mathbb{P}(U\cap L)\geq\mathbb{P}(A\cap B)=1-\mathbb{P}(A^{\mathsf{c}})-\mathbb{P}(B^{\mathsf{c}}).
The theorem will follow from choices of
a
and
b
that help bound
\mathbb{P}(A^{\mathsf{c}})
and
\mathbb{P}(B^{\mathsf{c}})
.
Using the fact that
a<p
, along with the union bound and Lemma
1
, we have
\mathbb{P}(A^{\mathsf{c}})=\mathbb{P}(Z<a)\leq\mathbb{P}(Z\leq a)\leq r\cdot\mathbb{P}(X_{1}\leq a)\leq r\cdot 2^{-n\textsf{KL}(a\|p)+4\log(n+1)+\left[\log\frac{p}{1-p}\right]_{+}}.
Suppose
\textsf{KL}(0\|p)\geq\frac{\log r+\Delta(\delta,p,n)}{n}
. Since
\textsf{KL}(p\|p)=0
, and KL is continuous by its first argument, by intermediate value theorem, we can choose
0\leq a<p
such that
\begin{split}\textsf{KL}(a\|p)&=\frac{\log r+\Delta(\delta,p,n)}{n}\\
&=\frac{\log r+\log\frac{1}{\delta/2}+4\log(n+1)+\left[\log\frac{p}{1-p}\right]_{+}}{n},\end{split}
(3)
which gives
r\cdot 2^{-n\textsf{KL}(a\|p)+4\log(n+1)+\left[\log\frac{p}{1-p}\right]_{+}}=\delta/2
.
Thus, by choosing
0\leq a<p
according to (
3
), we get
\mathbb{P}(A^{\mathsf{c}})\leq\frac{\delta}{2}
.
If
\textsf{KL}(0\|p)<\frac{\log r+\Delta(\delta,p,n)}{n}
, in other words, there is no
0\leq a<p
satisfying (
3
), then take
a=0
. And in this case, the upper bound of the theorem trivially holds for any
Z<p
because
\displaystyle\mathbb{P}\left(\textsf{KL}(b\|p)\leq\textsf{KL}(Z\|p)\leq\textsf{KL}(0\|p)<\frac{\log r+\Delta(\delta,p,n)}{n}\right)
\displaystyle\geq\mathbb{P}(0\leq Z\leq b)=1-\mathbb{P}(Z>b).
On the other hand, by the independence of data points, we have:
\mathbb{P}(B^{\mathsf{c}})=\mathbb{P}(Z>b)=(1-\mathbb{P}(X_{1}\leq b))^{r}.
(4)
Using the inequality
\forall x\in[0,1],k>0:(1-x)^{k}\leq e^{-kx}
and Lemma
1
, we have
(1-\mathbb{P}(X_{1}\leq b))^{r}\leq\exp\left(-r\cdot\mathbb{P}(X_{1}\leq b)\right)\leq\exp\left(-r\cdot 2^{-n\textsf{KL}(b\|p)-4\log(n+1)-\left[\log\frac{p}{1-p}\right]_{+}}\right).
(5)
Suppose
\textsf{KL}(0\|p)\geq\frac{\log r-\log\ln\frac{1}{\delta/2}-4\log(n+1)-\left[\log\frac{p}{1-p}\right]_{+}}{n}
, again by the intermediate value theorem, we can choose
0\leq b<p
such that
\textsf{KL}(b\|p)=\frac{\log r-\log\ln\frac{1}{\delta/2}-4\log(n+1)-\left[\log\frac{p}{1-p}\right]_{+}}{n},
(6)
which gives
\exp\left(-r\cdot 2^{-n\textsf{KL}(b\|p)-4\log(n+1)-\left[\log\frac{p}{1-p}\right]_{+}}\right)=\delta/2
.
Thus, by choosing
0\leq b<p
according to (
6
), we get
\mathbb{P}(B^{\mathsf{c}})\leq\frac{\delta}{2}
.
If
\textsf{KL}(0\|p)<\frac{\log r-\log\ln\frac{1}{\delta/2}-4\log(n+1)-\left[\log\frac{p}{1-p}\right]_{+}}{n}
, in other words, there is no
0\leq b<p
satisfying (
6
), then by combining (
4
) and (
5
),
\mathbb{P}(Z>0)\leq\exp\left(-r\cdot 2^{-n\textsf{KL}(0\|p)-4\log(n+1)-\left[\log\frac{p}{1-p}\right]_{+}}\right)\leq\frac{\delta}{2}.
So in this case, we have with probability
\geq\frac{\delta}{2}>1-\delta
,
Z=0
.
Therefore, by choosing
a
and
b
as above, we get
\mathbb{P}\Big(\textsf{KL}(Z\|p)\in\big(\textsf{KL}(b\|p),\textsf{KL}(a\|p)\big)\Big)=\mathbb{P}(U\cap L)\geq 1-\mathbb{P}(A^{\mathsf{c}})-\mathbb{P}(B^{\mathsf{c}})\geq 1-\delta,
with
\textsf{KL}(a\|p)
and
\textsf{KL}(b\|p)
as in (
3
) and (
6
) respectively. Except that if
\textsf{KL}(0\|p)<\frac{\log r-\Delta(\delta,p,n)}{n}
, then with probability
>1-\delta
,
Z=0
.
The theorem follows by widening this interval, to get a symmetric expression.
Remark 1
.
The term
\left[\log\frac{p}{1-p}\right]_{+}
is not actually needed in the upper bounds in Lemma
1
and Theorem
1
, and is included in the Theorem statement only for the sake of a symmetric and concise statement.
Remark 2
.
The upper bound in Theorem
1
does not rely on
X_{i}
being independent, nor even identically distributed. In fact, as long as
X_{i}\sim\frac{1}{n}\textnormal{Bin}(n,p_{i})
marginally with
p_{i}\geq p
, the upper bound still holds. This union-bound based upper bound can be viewed as a (one sided) concentration guarantee, thinking of each
X_{i}
as an empirical average with mean
p
, and ensuring that all
n
empirical measurements are close to their expectation (or rather, not much smaller than their expectation). In a machine learning context,
X_{i}
would correspond to the empirical error of predictor
i
, with population error
p
(or in the more general non-identically-distributed case, with population error
p_{i}\geq p
). Viewed this way, the upper bound in Theorem
1
is a special case
1
1
1
Theorem
1
is a special case where we take a discrete uniform prior over the
r
predictors, and are concerned only with point-mass posteriors.
of the PAC-Bayes bound as presented by
McAllester 2003
following
Langford and Seeger 2002
. The upper bound is thus similar to, but slightly tighter than, common concentration guarantees based on a similar union-bound argument, but relying on the Hoeffding and Bernstein bounds on the Binomial CDF instead of the KL-based bound of Lemma
1
. Theorem
1