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: Where the conjecture holds

  • 1
    $\begingroup$ 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)$. $\endgroup$ – A.S. Dec 8 '15 at 19:50
  • $\begingroup$ @A.S. Can you expand your reasoning a bit? What is the "ration of odds"? $\endgroup$ – Thomas Ahle Dec 8 '15 at 20:20
  • 1
    $\begingroup$ 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. $\endgroup$ – A.S. Dec 8 '15 at 20:25
  • $\begingroup$ 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. $\endgroup$ – Thomas Ahle Dec 14 '15 at 11:26
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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! $\endgroup$ – Rafer Aug 22 '16 at 6:02
  • $\begingroup$ @Rafer It's just Stirling's approximation on the three factors, and then some crude bounds to get the 8. $\endgroup$ – Thomas Ahle Sep 12 '16 at 9:05

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.