5
$\begingroup$

Given $\epsilon > 0$, what is the minimal $d$, such that $\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{d} \ge \epsilon 2^n$? Is there a clean answer?

$\endgroup$
1
  • $\begingroup$ For many values of epsilon less than 1/2, d will be such that n choose d is close to epsilon2^n, or one more. For many epsilon between 1/2 and 1, you can use an analogous value based on n-d. It is an interesting exercise to find how close to 1/2 that finding such a value becomes challenging. Perhaps others will give you references to other MathOverflow questions where this sum has been discussed. Gerhard "Too Lazy To Search Now" Paseman, 2013.01.24 $\endgroup$ Jan 25, 2013 at 1:17

1 Answer 1

10
$\begingroup$

There's no clean answer, but you need to use the Central Limit Theorem. If $X_1,\ldots, X_n$ are independent random variables taking values 0 and 1 with probability $1/2$, then you're asking for a $d$ such that $\mathbb P(S_n\le d)\ge \epsilon$. By the Central limit theorem, for large $n$, you have $S_n$ is well approximated by a normal distribution with mean $n/2$ and variance $n/4$. That is $S_n$ has approximately the same distribution as $n/2+\sqrt n/2 N$ where $N$ is a Normal(0,1) random variable.

In this language, you are now asking for $d$ such that $\mathbb P(N\le (2d-n)/\sqrt n)\approx\epsilon$, or $\Phi((2d-n)/\sqrt n)\approx\epsilon$.

If you solve $\Phi(x)=\epsilon$, then you can obtain a suitable value for $d$ is something like $n/2-\sqrt{-2n\log\epsilon}$.

$\endgroup$
2
  • $\begingroup$ Thanks. Do you know how to solve $\Phi(x) = \epsilon$? $\endgroup$
    – jsliyuan
    Jan 26, 2013 at 7:45
  • $\begingroup$ I did in my answer. That question really doesn't belong on this site. You can find books that compute the asymptotices of the error function, or probably wikipedia also. $\endgroup$ Jan 26, 2013 at 17:58

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.