Binomial Tail Bounds and Relative Entropy

Why Binomial Tails Have a Relative-Entropy Exponent

A binomial random variable counts successes in repeated trials with the same success probability. When the observed success fraction is far from that probability, its tail probability can be small, often on an exponential scale in the number of trials. Chernoff’s method makes this precise: an exponential transform gives a bound, and optimizing its parameter produces an exponent with a recognizable information-theoretic form.

The key quantity is the Kullback–Leibler divergence between two Bernoulli distributions. In this setting, one Bernoulli distribution has the trial’s actual success probability \(p\); the other has success probability equal to the tail threshold \(x\). The divergence measures the exponential cost associated with a success fraction \(x\) that differs from \(p\).

The order of the arguments matters: \(D(x\|p)\) is generally not the same as \(D(p\|x)\). The threshold fraction \(x\) is the first argument; the binomial model’s success probability \(p\) is the second. For \(x\) in \((0,1)\), differentiating with respect to \(x\) gives

Thus \(D(x\|p)\) is strictly convex as a function of \(x\), has its minimum at \(x=p\), and that minimum is \(D(p\|p)=0\). In particular, the divergence is positive whenever \(x\neq p\).

The Binomial Tail Bound

Suppose \(X\sim\operatorname{Bin}(n,p)\), where \(n\) is a positive integer and \(0<p<1\). Equivalently, write \(X=Y_1+\cdots+Y_n\), where the \(Y_i\) are independent Bernoulli random variables with \(P(Y_i=1)=p\) and \(P(Y_i=0)=1-p\). For any real \(t\),

This moment-generating function is the input to exponential Markov bounds. For the upper tail, take \(t>0\); for the lower tail, take \(t<0\). The sign determines which tail event implies a large value of the nonnegative variable to which Markov’s inequality is applied.

Here is the full optimization for interior thresholds. When \(p<x<1\), the exponential Markov inequality gives, for every \(t>0\),

The logarithm of the right-hand side, divided by \(n\), is \(-tx+\log(1-p+pe^t)\). Its derivative with respect to \(t\) is \(-x+pe^t/(1-p+pe^t)\). Setting this derivative to zero gives

Since \(x>p\), the ratio inside the logarithm exceeds \(1\), so \(t_*>0\) is an admissible upper-tail parameter. Substitution gives \(1-p+pe^{t_*}=(1-p)/(1-x)\). Therefore

This proves the upper-tail inequality for \(p<x<1\). At \(x=p\), the choice \(t=0\) gives the bound \(1\). At \(x=1\), the event is \(X=n\), which has probability \(p^n=\exp\{-nD(1\|p)\}\).

For the lower tail, let \(0<x<p\) and choose \(t<0\). If \(X\leq nx\), then \(e^{tX}\geq e^{tnx}\), so

The same derivative equation gives \(t_*= \log(x(1-p)/(p(1-x)))\). This time \(x<p\), so \(t_*<0\), as required. Substitution again gives \(-D(x\|p)\) for the logarithm of the optimized bound divided by \(n\). At \(x=p\), the bound is \(1\); at \(x=0\), \(P(X\leq0)=(1-p)^n=\exp\{-nD(0\|p)\}\). This proves both claims. \(\square\)

Worked Applications

Thresholds, Interpretation, and a Common Pitfall

For integer thresholds, set \(x=k/n\). If \(k\) is an integer with \(k\geq np\), then \(P(X\geq k)\leq\exp\{-nD(k/n\|p)\}\). If \(k\leq np\), then \(P(X\leq k)\leq\exp\{-nD(k/n\|p)\}\). If a requested threshold is not an integer, the event still has its literal meaning: for example, \(X\geq nx\) is equivalent to \(X\geq\lceil nx\rceil\). The theorem’s bound at the real threshold \(nx\) remains valid because the event itself implies \(X\geq nx\).

The exponent scales linearly with \(n\). For a fixed threshold fraction \(x\neq p\), the bound is \(\exp\{-nD(x\|p)\}\), so increasing the number of trials makes the bound decrease exponentially. The divergence is the rate in this bound: larger separation between the threshold fraction and \(p\) generally means a larger exponent. This connects the binomial tail calculation to the convex rate-function perspective of Chernoff optimization.

Common mistake: using the wrong sign for the exponential parameter. For an upper tail, a student might take \(t<0\) and write \(P(X\geq nx)\leq e^{-tnx}E[e^{tX}]\). But when \(t<0\), \(X\geq nx\) implies \(e^{tX}\leq e^{tnx}\), not \(e^{tX}\geq e^{tnx}\); the Markov step does not follow. The correction is to use \(t>0\) for the upper tail. For the lower tail, use \(t<0\), because \(X\leq nx\) then implies \(e^{tX}\geq e^{tnx}\).

A second useful check is that the bound is \(1\) when \(x=p\), since \(D(p\|p)=0\). A threshold on the wrong side of the mean does not give the corresponding one-sided exponential bound by this optimization: for instance, an upper-tail threshold below \(p\) is not a rare upper-tail event, and the claimed rate would not describe it.