MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Maple seems to suggest that for any real $a\ge 1$ and positive integer $K$ and $n$ with $K\le n/(a+1)$ one has $$ a^n + na^{n-1} + \binom{n}{2}a^{n-2} +...+ \binom{n}{K}a^{n-K} \le a^{n-K} e^{nH(K/n)}, $$ where $H(x)=-x\log(x)-(1-x)\log(1-x)$ is the entropy function.

An essentially equivalent form is as follows. Suppose that $X\sim B(n,p)$, where $p<1/2$, and let $q:=1-p$. Then for any $\alpha\le 1$, $$ \mathsf{Pr}(X\le\alpha pn) \le p^{\alpha pn}q^{(1-\alpha p)n}e^{nH(\alpha p)}. $$

I believe this should be well-known (if at all true). Can anybody suggest a reference?

share|cite|improve this question
I haven't looked in detail, but this paper seems promising: – Mark Meckes Apr 21 '11 at 15:46
Sorry to bump an old post, but the 'equivalent form' is called the "Chernoff bound" and can currently be found on Wikipedia[1]. In particular, this version is normally stated, for $\beta < p$, as $\Pr[X \leq \beta n] \leq e^{-n D(\beta, p)}$ where $D(\beta,p)$ is the KL-divergence between Bernoullis with probabilities $\beta$ and $p$. [1] – usul Feb 16 at 7:10
@usul: Thank you! – Seva Feb 16 at 10:30
up vote 3 down vote accepted

After a little thinking, there is a strikingly simple proof, running as follows.

Dividing through both sides of the inequality by $a^{n-K}$, we see that the larger is $a$, the stronger the estimate is. Thus, the general case will follow from that where $K=n/(a+1)$. For brevity we write $p:=K/n$ and $q:=1-p$, so that $a=q/p$ and $a+1=p^{-1}$. The inequality in question can now be re-written as $$ \sum_{j=0}^K \binom nj a^{n-j} \le a^{qn} e^{nH(p)}. $$ Since the left-hand side does not exceed $(a+1)^n=p^{-n}$, it suffices to show that $$ p^{-n} \le a^{qn} e^{nH(p)}; $$ that is, $$ p^{-n} a^{-qn} \le e^{nH(p)}. $$ However, the left-hand side is equal to $$ p^{-n} (q/p)^{-qn} = p^{-pn} q^{-qn} = e^{nH(p)}, $$ which completes the proof.

Although the proof is almost vacuous, the inequality is surprisingly sharp: numerical computations suggest that the right-hand side is always at most twice larger than the left-hand side.

share|cite|improve this answer

You can find a basic large deviation inequality in lecture 16 of Sinai's "Probability Theory". Define $ R(\lambda)=E[e^{\lambda X}]$ for a random variable $X$, and let $m(\lambda)=R'(\lambda)/R(\lambda)$. Let $c>m=E[X]$ and $\lambda_0$ be such that $m(\lambda_0)=c.$ Then we have

$$ P \ [X_1+ \cdots +X_n > cn] \le B_n (R(\lambda_0)e^{-\lambda_0 c})^n $$

and $B_n \to 1/2$ as $n \to \infty$. Here $X_i$ are i.i.d with the same distribution as $X$.

Now, for the case you are interested in $R(\lambda)=pe^{\lambda}+1-p$ and you can easily compute $\lambda_0=\log (c(1-p)/p(1-c))$. I think if you compute the right hand side you will get something which is quite close to what you need.

share|cite|improve this answer
There are lots of large deviation inequalities. What I'd be happy to have is a reference to the specific inequality that I need, not a way to prove yet another inequality. Also, it seems that the approach you have outlined does not yield an explicit bound, due to the presence of the factor $B_n$. – Seva Apr 21 '11 at 13:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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