# Sharper Lower Bounds for Binomial/Chernoff Tails

The Wikipedia page for the Binomial Distribution states the following lower bound, which I suppose can also be generalized as a general Chernoff lower bound.

$$\Pr(X \le k) \geq \frac{1}{(n+1)^2} \exp\left(-nD\left(\frac{k}{n}\left|\right|p\right)\right) \quad\quad\mbox{if }p<\frac{k}{n}<1$$

Clearly this is tight up to the $(n+1)^{-2}$ factor.

However computationally it seems that $(n+1)^{-1}$ would be tight as well. Even (n+1)^{-.7} seems to be fine.

It's not as easy to find lower bounds for tails as it is upper, but for the Normal Distribution there seems to be a standard bound:

$$\int_x^\infty e^{-t^2/2}dt \ge (1/x-1/x^3)e^{-x^2/2}$$

My question is thus, is the $\frac{1}{(n+1)^2}$ factor the best known? Or can $\frac{1}{n+1}$ be shown to be sufficient?

Update: Here is the region in which the conjecture holds numerically, by Mathematica:

• Asymptotically, $P(X\ge an)\sim \frac 1{1-r}\frac 1{\sqrt{2\pi a(1-a)n}}e^{-nD(a||p)}$ for $r$ ration of odds of $Bern(p)$ and $Bern(a)$. – A.S. Dec 8 '15 at 19:50
• @A.S. Can you expand your reasoning a bit? What is the "ration of odds"? – Thomas Ahle Dec 8 '15 at 20:20
• I mistyped. Ratio of odds, where odds of $Bern(p)$ is classical odds $\frac p{1-p}$. See the survey I linked in the formula for a beautiful Cramer's proof that relies on local CLT. – A.S. Dec 8 '15 at 20:25
• Thank you for the reference, looks like we may state it as $P(X\ge an)= \frac {a(1-p)}{a-p}\frac 1{\sqrt{2\pi a(1-a)n}}e^{-nD(a||p)}(1+O(1/n))$. Cramer's proof is indeed very nice. Feel free to add it as a real answer to the question. – Thomas Ahle Dec 14 '15 at 11:26
• That looks about right. It's also worth noting that $D(p+\epsilon||p)\sim\frac {\epsilon^2}{2p(1-p)}$, so that $n=\omega(\epsilon^{-1/2})$ for the bound to be meaningful. It also matches standard gaussian tail asymptotics as expected. – A.S. Dec 14 '15 at 17:02

It looks like I can at least show $(n+1)^2$ can be improved to $\sqrt{2n}$:

\begin{align} \sum_{i=0}^k {n \choose i} p^i (1-p)^{n-i} &\ge {n \choose k} p^k (1-p)^{n-k}\\ &= {n \choose k} \exp\left(-n(k/n \log1/p+(1-k/n)\log1/(1-p)\right)\\ &\ge \frac{\exp(n\text{H}(k/n))}{\sqrt{8k(1-k/n)}}\, \exp(-n(\text{D}(k/n||p) + H(k/n)))\\ &= \frac{1}{\sqrt{8k(1-k/n)}}\exp(-n\text{D}(k/n||p))\\ &\ge \frac{1}{\sqrt{2n}}\exp(-n\text{D}(k/n||p)) \end{align}

Here I've used the lower bound for the binomial ${n\choose an}\ge\frac1{8na(1-a)}\exp(n\text{H}(a))\\$ from http://www.lkozma.net/inequalities_cheat_sheet/ineq.pdf . I'd be happy if anyone can provide a better reference.

We see that it is sharp in the sense that ${2\choose1} = \frac1{\sqrt{2\cdot2}}\exp(2\text{H}{(1/2)})$. Also by A.S.'s comments we see that the bound is asymptotically sharp, up to a constant dependent on $p$ and $k$.

Update: R.B. Ash. Information Theory is a reference to the binomial approximation, and in fact they also derive the exact same bound for the distribution.

• Hi Thomas, can you show the details about how you derive the inequality $n \choose an$ $\ge$ $\frac{1}{8na(1-a)}e^{nH(a)}$ ? Thanks! – Rafer Aug 22 '16 at 6:02
• @Rafer It's just Stirling's approximation on the three factors, and then some crude bounds to get the 8. – Thomas Ahle Sep 12 '16 at 9:05