A large deviation / binomial coefficients bound - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T19:44:52Z http://mathoverflow.net/feeds/question/62510 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62510/a-large-deviation-binomial-coefficients-bound A large deviation / binomial coefficients bound Seva 2011-04-21T09:19:58Z 2011-04-23T20:21:39Z <p>Maple seems to suggest that for any real $a\ge 1$ and positive integer $K$ and $n$ with <code>$K\le n/(a+1)$</code> one has <code>$$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)},$$</code> where <code>$H(x)=-x\log(x)-(1-x)\log(1-x)$</code> is the entropy function.</p> <p>An essentially equivalent form is as follows. Suppose that <code>$X\sim B(n,p)$</code>, where $p&lt;1/2$, and let $q:=1-p$. Then for any $\alpha\le 1$, <code>$$\mathsf{Pr}(X\le\alpha pn) \le p^{\alpha pn}q^{(1-\alpha p)n}e^{nH(\alpha p)}.$$</code></p> <p>I believe this should be well-known (if at all true). Can anybody suggest a reference?</p> http://mathoverflow.net/questions/62510/a-large-deviation-binomial-coefficients-bound/62514#62514 Answer by Keivan Karai for A large deviation / binomial coefficients bound Keivan Karai 2011-04-21T10:02:05Z 2011-04-21T10:02:05Z <p>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> <p>$$P \ [X_1+ \cdots +X_n > cn] \le B_n (R(\lambda_0)e^{-\lambda_0 c})^n$$</p> <p>and $B_n \to 1/2$ as $n \to \infty$. Here $X_i$ are i.i.d with the same distribution as $X$.</p> <p>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. </p> http://mathoverflow.net/questions/62510/a-large-deviation-binomial-coefficients-bound/62556#62556 Answer by Seva for A large deviation / binomial coefficients bound Seva 2011-04-21T18:10:33Z 2011-04-23T20:21:39Z <p>After a little thinking, there is a strikingly simple proof, running as follows.</p> <p>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.</p> <hr> <p>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.</p>