# Tail Bound on Binomial

Context: circuit complexity argument:

How do I show that $$\sum_{i=0}^{n/2- \sqrt{n}} {n \choose i} \geq 2^n/50$$ ? (as n goes to infinity)

[This shows up in proving Mod2 is not in ACC(3)].

Standard approach would be to use chernoff bounds; but it provides the wrong direction.

Thanks!

-

If $X_n$ is a binomial random variable with parameters $n$ and $p=1/2$, this inequality says $P(X_n \le n/2 -\sqrt{n}) \ge 1/50$. By the deMoivre-Laplace Theorem, $Z_n = (2X_n - n)/\sqrt{n}$ converges in distribution as $n \to \infty$ to a standard normal distribution, and thus $P(X_n \le n/2 - \sqrt{n}) = P(Z_n \le -2) \to \Phi(-2) \approx .0227501320 > 1/50$ where $\Phi$ is the cumulative distribution function of the standard normal distribution. So your inequality is true for sufficiently large $n$.
Yes indeed, and the Berry-Esseen inequality will give an explicit value of $n$ beyond which it is true, small enough that the gap can be easily filled by computation. Actually $n=23$ is the largest value for which the inequality fails. – Brendan McKay Oct 3 '11 at 13:13
No, there are many values greater than 23 for which it fails. The largest is 307, I think: for $n = 307$, $n/2 - \sqrt{n} \approx 135.9785845$ and $P(X_{307} \le 135) \approx .01987042485$. – Robert Israel Oct 4 '11 at 6:38