3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I haven't looked in detail, but this paper seems promising: springerlink.com/content/b375207127137544 $\endgroup$ Apr 21, 2011 at 15:46
  • $\begingroup$ Sorry to bump an old post, but the 'equivalent form' is called the "Chernoff bound" and can currently be found on Wikipedia[1]. In particular, this version is normally stated, for $\beta < p$, as $\Pr[X \leq \beta n] \leq e^{-n D(\beta, p)}$ where $D(\beta,p)$ is the KL-divergence between Bernoullis with probabilities $\beta$ and $p$. [1]en.wikipedia.org/wiki/Chernoff_bound $\endgroup$
    – usul
    Feb 16, 2016 at 7:10
  • $\begingroup$ @usul: Thank you! $\endgroup$
    – Seva
    Feb 16, 2016 at 10:30

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Seva
    Apr 21, 2011 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.