3
$\begingroup$

For a small $c>0$, what is a smallest $k$ such that $$\sum_{i=0}^k \binom{n}{i} \ge c \cdot 2^n.$$

The sum jumps somewhere around $k=\frac{n}2$ from $o(2^n)$ to almost $2^n$. Is there a better estimate than $k=\frac{n}{2}+o(n)$?

$\endgroup$
2
$\begingroup$

This is called central limit theorem. You ask for $P(S_n\le k)$ to be about $c$, where $S_n$ is binomial $(n,1/2)$. Since $S_n$ has expectation $n/2$ and variance $n/4$, for every fixed $x$, $$ P(S_n\le n/2+x\sqrt{n}/2) $$ converges to $P(Z\le x)$ where $Z$ is centered standard Gaussian. Reasoning backwards, pick $x$ such that $P(Z\le x)=c$, that is, $$ \int_{-\infty}^x\mathrm{e}^{-z^2/2}\mathrm{d}z/\sqrt{2\pi}=c, $$ and choose for $k$ the integer part of $$ n/2+x\sqrt{n}/2. $$

$\endgroup$
  • $\begingroup$ Sneaky downvote, six years later... Nice. $\endgroup$ – Did Apr 9 '17 at 15:05
2
$\begingroup$

Let $X$ be the random variable which represents the result of tossing a fair coin $n$ times. Then $$\sum_{i=0}^k 2^{-n}\binom{n}{i}$$ is the probability that $X \le k$.

This probability is well-approximated by the probability that a normally distributed random variable with mean $n/2$ and standard deviation $\sqrt{n}/2$ is $\le k$. It is convenient to express this probability as usual in terms of the standard normal. We end up with an integral which is relatively easy to approximate, using simple estimates based on integration by parts, or more sophisticated estimates.

$\endgroup$

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.