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?
-
$\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$– Gerhard PasemanJan 25, 2013 at 1:17
1 Answer
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}$.
-
$\begingroup$ Thanks. Do you know how to solve $\Phi(x) = \epsilon$? $\endgroup$– jsliyuanJan 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