1
$\begingroup$

Suppose we throw a coin $2n$ times. The probability of $n$ times heads (and therefore $n$ times tails) is $$P(\text{"n times heads"}) = \frac{1}{4^n}\binom{2n}{n}.$$ We can use Stirling's formula to get the asymptotics $$\frac{1}{4^n}\binom{2n}{n} \sim \frac{1}{\sqrt{\pi n}} $$ as $n\to \infty$. Now I want to throw the coin $3n$ times and look at the probability of the event $$P(\text{"twice as often heads than tails"}) = \frac{1}{8^n}\binom{3n}{2n}.$$ Is there any "nice" asymptotics for this too? I tried using Stirling's formula again, but it does not seem to be as nice as it could get.

$\endgroup$
  • 1
    $\begingroup$ I'm sure Stirling works just as well. $\endgroup$ – Lord Shark the Unknown Oct 22 '17 at 14:33
  • $\begingroup$ @LordSharktheUnknown. It must just as you wrote ! $\endgroup$ – Claude Leibovici Oct 22 '17 at 14:51
3
$\begingroup$

Simply use that $$ \log {3n \choose 2n} = 3n\log(3n)-3n -2n\log(2n)+2n-n\log(n)+n +O(\log(n)) = n\log\left(\frac{27}{4}\right) $$ implies that

$$ P("\text{twice as often heads than tails}") \sim \frac{1}{8^n} \frac{27^n}{4^n} = \frac{27^n}{32^n} \ll 1 $$

$\endgroup$
  • $\begingroup$ Can you explain how you obtain the logarithm identity? $\endgroup$ – Staki42 Oct 22 '17 at 16:09
  • $\begingroup$ I simply use the logarithm of Stirlings formula: $ n! \sim n^n e^{-n} \sqrt{2\pi n}$ implies that $\log n! = n\log(n) - n + O(\log(n))$. $\endgroup$ – Cyclone Oct 22 '17 at 16:10
  • $\begingroup$ Oh, I see. Thanks! $\endgroup$ – Staki42 Oct 22 '17 at 16:14
  • $\begingroup$ The end result is not correct, the $O(\log n)$ term does matter. See my answer below. $\endgroup$ – A.G. Oct 22 '17 at 17:27
  • $\begingroup$ It is correct, precisely in an asymptotic sense. The symbol $A\sim B$ as $n\to \infty$ is defined (!) as $\lim_{n\to \infty} A(n)/B(n)=1$. The additional factor you added is helpful, because it is one order higher in the expansion but it does by no means imply that my result is false. The OP was just asking for an asymptotic expression, which I have given. $\endgroup$ – Cyclone Oct 22 '17 at 18:22
2
$\begingroup$

Suppose that we toss a fair coin $N$ times. What is the probability that we get $p N$ heads and $(1-p)N$ tails? It is $2^{-N}{N \choose pN}$. Now, $${N \choose pN} \approx 2^{-H(p) N},$$ where $H(p)$ is the binary entropy function, defined as $H(p) = p \log_2\frac1p + (1-p) \log_2 \frac{1}{1-p}$ (see also https://en.wikipedia.org/wiki/Binary_entropy_function). Thus, the probability of the desired event is approximately $2^{(-1 + H(p)) N}$.

Plugging in $N = 3n$ and $p = 1/3$, we get that the probability is approximately $(27/32)^n$.

$\endgroup$
  • 1
    $\begingroup$ +1 for the binary entropy function, I didn't know it yet. $\endgroup$ – Cyclone Oct 22 '17 at 15:16
1
$\begingroup$

Using Stirling's approximation you get $$\begin{align} P(\text{twice as many heads}) &= {3n\choose 2n}(1/2)^{3n}\\ &= \frac{(3n)!}{(2n)! \ n!\ 2^{3n}}\\ &\approx { (3n)^{3n}\ e^{-3n}\ \sqrt{6\pi n} \over (2n)^{2n}\ e^{-2n}\ \sqrt{4\pi n}\ (n)^{n}\ e^{-n}\ \sqrt{2\pi n}\ 2^{3n}}\\ &= \sqrt{3\over 4\pi n}\ \left({27\over32}\right)^n. \end{align} $$ Numerical precision is quite good ; for $n=50$ for instance $$ \begin{align} P(\text{twice as many heads})&= {3n\choose 2n}(1/2)^{3n} =0.0000141031 \\ \quad\text{and}\quad \sqrt{3\over 4\pi n}\ \left({27\over32}\right)^n&=0.0000141306. \end{align} $$

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