# Asymptotics of $3n$ coin flips

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.

• I'm sure Stirling works just as well. Commented Oct 22, 2017 at 14:33
• @LordSharktheUnknown. It must just as you wrote ! Commented Oct 22, 2017 at 14:51

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

• Can you explain how you obtain the logarithm identity? Commented Oct 22, 2017 at 16:09
• 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))$. Commented Oct 22, 2017 at 16:10
• Oh, I see. Thanks! Commented Oct 22, 2017 at 16:14
• The end result is not correct, the $O(\log n)$ term does matter. See my answer below.
– A.G.
Commented Oct 22, 2017 at 17:27
• 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. Commented Oct 22, 2017 at 18:22

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

• +1 for the binary entropy function, I didn't know it yet. Commented Oct 22, 2017 at 15:16

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}