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 Paseman Jan 25 '13 at 1:17

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$ – jsliyuan Jan 26 '13 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$ – Anthony Quas Jan 26 '13 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.