## 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 2011 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 2011 at 13:42