12
$\begingroup$

For each positive even integer $n$, set

$$P_n = \displaystyle {{n} \choose {\frac{n}{2}}}\frac{1}{2^n}.$$

Show that $\displaystyle \lim_{n \to \infty} P_n$ exists and determine its value.

Here's what I have so far: each $P_n$ can be thought of as the probability of tossing a fair coin $n$ times, and obtaining exactly $\frac{n}{2}$ heads. My expectation is that $P_n \to 1$, since in any large trial, one would expect to record just about as many heads as tails. But I'm not sure how to mathematically justify this hunch.

Hints or solutions are greatly appreciated.

$\endgroup$
2
  • 2
    $\begingroup$ It very strikingly does not have limit $1$. $\endgroup$ – André Nicolas Jan 28 '13 at 3:53
  • 2
    $\begingroup$ It seems likely that $\dfrac{\text{heads}}{\text{tosses}}\to \frac{1}{2}$ as $n\to\infty$, but not that the number of heads and tails are likely to be exactly equal when $n$ is large. $\endgroup$ – Jonas Meyer Jan 28 '13 at 3:54
2
$\begingroup$

Show that the sequence is a monotone decreasing sequence and since it is positive, the limit must exist.

Using Stirling, we get that $n! \sim \sqrt{2 \pi n} \left(\dfrac{n}e \right)^n$. Hence, $$\dbinom{n}{n/2} \sim \dfrac{4^{n/2}}{\sqrt{\pi n/2}} = \dfrac{2^{n+1/2}}{\sqrt{n \pi}}$$ Now conclude the limit. (Stirling's approximation is a bit too big hammer for your needs. You can conclude that the limit is $0$, even without resorting to Stirling.)

$\endgroup$
6
$\begingroup$

Here's another approach! Write $n=2m:$

$$\binom{2m}{m}\frac{1}{4^m}=\frac{1}{\pi}\int_0^1 t^{-\frac{1}{2}}(1-t)^{m-\frac{1}{2}}dt$$

The integrand tends to $0$ as $m\to \infty$

$\endgroup$
1
  • $\begingroup$ Very nice! ${ }$ $\endgroup$ – user940 Jan 28 '13 at 13:09
6
$\begingroup$

$$\left[ {n\choose n/2}{1\over 2^n}\right]^2={1\over n+1}\prod_{j=1}^{n/2}\left(1-{1\over 4j^2}\right) \leq{1\over n+1}\to 0.$$

$\endgroup$
3
$\begingroup$

This number is $0$ as you have written it.

There is the deMoivre-Laplace limit theorem showing that biased coin tosses approach a bell curve in distribution.

\[ \mathbb{P}[k \text{ heads}]= \binom{n}{k} p^k q^{n-k} \to \frac{1}{\sqrt{2\pi n pq} } e^{-(k - np)^2/2npq} \]

In our case, $p = 1/2, k = n/2$

\[ \mathbb{P}[n/2 \text{ heads}]= \binom{n}{n/2} \frac{1}{2^n} \approx \sqrt{\frac{2}{\pi n} } \to 0\]


The Law of Large Numbers says $\displaystyle \mathbb{P}\left[\lim_{n \to \infty} \frac{\# \text{heads} }{n} = \frac{1}{2}\right]=1$.

In other words, the observed fraction of heads always tends to 1/2. These odds can be $1/2 - \epsilon \text{ or }1/2 + \epsilon$.

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