MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question

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|cite|improve this answer
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


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.