Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
I haven't looked in detail, but this paper seems promising: springerlink.com/content/b375207127137544 –  Mark Meckes Apr 21 '11 at 15:46
add comment

2 Answers 2

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.