# Sum of binomial coefficient

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?

• 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

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}$.
• Thanks. Do you know how to solve $\Phi(x) = \epsilon$? – jsliyuan Jan 26 '13 at 7:45