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

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!

share|improve this question

1 Answer 1

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$.

share|improve this answer
2  
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

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.