A large deviation / binomial coefficients bound - MathOverflow

A large deviation / binomial coefficients bound

2011-04-21T09:19:58Z

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?

Answer by Keivan Karai for A large deviation / binomial coefficients bound

2011-04-21T10:02:05Z

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.

Answer by Seva for A large deviation / binomial coefficients bound

2011-04-21T18:10:33Z

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.