Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 –  Gerhard Paseman Jan 25 '13 at 1:17
add comment

1 Answer 1

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

share|improve this answer
    
Thanks. Do you know how to solve $\Phi(x) = \epsilon$? –  jsliyuan Jan 26 '13 at 7:45
    
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. –  Anthony Quas Jan 26 '13 at 17:58
add comment

Your Answer

 
discard

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.