2
$\begingroup$

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!

$\endgroup$

1 Answer 1

7
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 3, 2011 at 13:13
  • $\begingroup$ 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$. $\endgroup$ Oct 4, 2011 at 6:38

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.