It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any idea how to show it. I tried some basic approximations but nothing worked. Thanks for your help.

  • 2
    $\begingroup$ Divide both sides by $2^{2n}$, now the left hand side is the probability that if you flip $2n$ coins you will get heads fewer than $.999n$ times. From here the key thing to look up is Chebyshev's inequality, and probably Sterling's approximation. Good luck. $\endgroup$ – Nate Mar 5 '14 at 20:26

We use Chernoff bound (alternatively Hoeffding's inequality) for binomial distribution.

With $X \sim B(2n, 1/2)$, we have by Chernoff bound,

$$ P(X\leq 0.999n) \leq \exp\left( -10^{-6} n \right). $$

On the other hand, by Stirling's formula, $$ P(X=n) \sim \frac 1{2^{2n}} \frac{\sqrt{2\pi \cdot 2n} \left( \frac {2n}e \right)^{2n}}{(\sqrt{2\pi n} )^2 \left(\frac ne\right)^{2n} } \sim \frac 1{\sqrt{\pi n}}. $$ Thus, for sufficiently large $n$, we have $$ P(X\leq 0.999n)< P(X=n).$$

Elementary way

We can avoid Chernoff bound and Stirling's formula, and prove this in a completely elementary way. As @Nate suggested, we apply Chebyshev inequality. $$ P(X\leq 0.999n)=\frac 12 P( |X- n|\geq 0.001n ) \leq \frac 12 \cdot \frac {\mathrm{Var}(X)}{(0.001n)^2} = \frac {250000 }n. $$ For the central probability, use $$ P(X=n)=\frac1{2^{2n}} \frac{(2n)!}{n!n!}=\frac{ 1 \cdot 3 \cdots (2n-1)}{2 \cdot 4 \cdots 2n}. $$ Then by squaring, we have $$ P(X=n)^2 = \left( \frac 12\right)^2 \left( \frac 34 \right)^2 \cdots \left(\frac{2n-1}{2n}\right)^2.$$ Then replace $\left(\frac 34\right)^2 $ by $\frac 23 \cdot \frac 34$, and $\left(\frac 56\right)^2 $ by $\frac 45\cdot \frac 56$, $\ldots$, lastly $\left(\frac{2n-1}{2n}\right)^2$ by $\frac{2n-2}{2n-1}\cdot\frac{2n-1}{2n}$. This gives $$ P(X=n)^2 \geq \frac 12 \cdot \frac 1{2n}=\frac1{4n}. $$ Now, we have $$ P(X=n)\geq \frac 1{2\sqrt n}. $$ Therefore, for $n> 500000^2$, we have $$ P(X\leq 0.999n)< P(X=n). $$


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.