# A large deviation / binomial coefficients bound

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?

-
I haven't looked in detail, but this paper seems promising: springerlink.com/content/b375207127137544 –  Mark Meckes Apr 21 '11 at 15:46

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.

-
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.
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