# Probability to get twice as many heads as tails at some point in an infinite sequence of coin tosses

Let consider an infinite sequence of tosses of a fair coin ($$p = 1/2$$ to get head or tail).

What is the probability to get, at least once, twice as many head as tails?

In another words, what is the probability that, there is $$n, k \in \Bbb N^*$$ such as $$H_{3n} = 2n, T_{3n} = n$$ (where $$H_n$$ denote the number of heads, and $$T_n$$ the number for tails at the $$n$$)?

What I tried: I don't even know how to start... I tried a lot of things but nothing really worked...

• What does it even mean to have "twice as many heads as tails" in an infinite sequence? Do you mean, for fixed $n$, what is the probability that there are twice as many heads as tails in the first $n$ tosses, and then take the limit as $n\to \infty$? In that case the answer is zero using any number of results, like Chebyshev's inequality.
– J.G
Jun 21, 2019 at 19:20
• To further question the quote in the above comment, does it need to be exactly twice as many or at least twice as many? Jun 21, 2019 at 19:24
• "What is the probabilty that, there is $n\in \Bbb N^*$ such as $H_{3n} = 2n, T_{3n} = n$ (where $H_n$ denote the number of heads, and $T_n$ the number for tails at the $n$-th toss. Jun 21, 2019 at 19:30
• And it needs to be exactly twice as many. Jun 21, 2019 at 19:40
• There's a lower bound of $\frac 38$ from the first three tosses. The event may happen at 6 tosses with $\frac{15}{64}$. So by inclusion-exclusion, we have a lower bound by the first six tosses of $\frac38+\frac{15}{64}-(\frac38)^2=\frac{15}{32}$, which is already almost $\frac12$ Jun 21, 2019 at 19:54

Probability of getting $$2k$$ heads and $$k$$ tails is $$\frac1{2^{3k}}\binom{3k}{k}$$. Thus the expected number of successes (getting twice as many heads as tails) is \begin{align} \sum_{k=1}^\infty\frac1{2^{3k}}\binom{3k}{k} &=\frac1{2\pi i}\sum_{k=1}^\infty\oint_{|z|=1^-}\left(\frac{\frac1z+z^2}2\right)^k\frac{\mathrm{d}z}z\\ &=\frac1{2\pi i}\oint_{|z|=1^-}\frac{\frac{\frac1z+z^2}2}{1-\frac{\frac1z+z^2}2}\frac{\mathrm{d}z}z\\ &=-\frac1{2\pi i}\oint_{|z|=1^-}\frac{1+z^3}{(1-z)(1-z-z^2)}\frac{\mathrm{d}z}z\\[6pt] &=\color{#C00}{\frac{\phi^3+1}{(\phi-1)(\phi+2)}}\color{#090}{-1}\\[6pt] &=\frac3{\sqrt5}\tag1 \end{align} Since the sum in the integral converges for $$|z|\lt1$$ and not for $$|z|\gt1$$, we integrate just inside the unit circle and therefore avoid the singularities at $$z=-\phi$$ and $$z=1$$. We catch the singularities at $$\color{#C00}{z=\frac1\phi}$$ and $$\color{#090}{z=0}$$.

Suppose that the probability of at least one success is $$p$$, then the probability of exactly $$k$$ successes is $$p^k(1-p)$$. Thus, the expected number of successes is $$\sum_{k=1}^\infty kp^k(1-p)=\frac p{1-p}\tag2$$ Since $$\frac p{1-p}=\frac3{\sqrt5}$$, the probability of at least one success is $$\bbox[5px,border:2px solid #C0A000]{p=\frac3{3+\sqrt5}}\tag3$$

Here is an alternate computation of $$(1)$$ that doesn't use contour integration. \begin{align} \sum_{k=1}^\infty\frac1{2^{3k}}\binom{3k}{k} &=\frac1{2\pi}\sum_{k=1}^\infty\int_0^{2\pi}\left(\frac{e^{-ix}+e^{2ix}}2\right)^k\,\mathrm{d}x\\ &=-\frac1{2\pi}\int_0^{2\pi}\frac{e^{3ix}+1}{e^{3ix}-2e^{ix}+1}\,\mathrm{d}x\\ &=-\frac1{2\pi}\int_0^{2\pi}{\scriptsize\left(\frac{10+3\sqrt5}5-\frac{\left(5+3\sqrt5\right)/5}{1-e^{-ix}/\phi}-\frac{\left(-5+3\sqrt5\right)/5}{1+e^{ix}/\phi}-\frac2{1-e^{ix}}\right)}\,\mathrm{d}x\\ &=-\left(\frac{10+3\sqrt5}5-\frac{5+3\sqrt5}5-\frac{-5+3\sqrt5}5-2\right)\\[3pt] &=\frac3{\sqrt5}\tag4 \end{align} Note that for $$|r|\lt1$$ \begin{align} \frac1{2\pi}\int_0^{2\pi}\frac1{1-re^{\pm ix}}\,\mathrm{d}x &=\frac1{2\pi}\int_0^{2\pi}\sum\limits_{k=0}^\infty r^ke^{\pm ikx}\,\mathrm{d}x\\ &=1\tag5 \end{align} and we take \begin{align} \frac1{2\pi}\int_0^{2\pi}\frac1{1-e^{ix}}\,\mathrm{d}x &=\lim_{r\to1^-}\frac1{2\pi}\int_0^{2\pi}\frac1{1-re^{ix}}\,\mathrm{d}x\\[3pt] &=1\tag6 \end{align}

• This is the same $57.2949\%$ that Robert Israel gets.
– robjohn
Jun 22, 2019 at 11:49
• Wow, I never thought like that. Thank a lot! Jun 22, 2019 at 11:53
• one question: could you explain me why $p^k(1-p$ is the probability to get $k$ successes? Jun 22, 2019 at 12:47
• The probability of getting no success is $1-p$. The probability of getting a success at some point is $p$ then getting no more is $1-p$. After getting any success, the probability of getting another is $p$ (since we still need to get twice as many heads as tails from that point) and the probability of getting no more is $1-p$. Thus, the probability of getting exactly $k$ successes is $p^k(1-p)$. Another way to look at it is that after each success, we are back to where we started in terms of the next success.
– robjohn
Jun 22, 2019 at 12:57
• that's totally clear thank's! Do you know how could I show that the sum egals $3/\sqrt5$ only using real analysis/power series? Jun 22, 2019 at 13:24

Let $$X_n = H_n - 2 T_n$$. This process forms a Markov chain; the conditional probabilities for $$X_n$$ given $$X_{n-1}$$ are $$1/2$$ for $$X_n = X_{n-1}+1$$ or $$X_{n-1}-2$$, $$0$$ otherwise. Let $$u(x)$$ be the probability of ever being at $$0$$ for this process starting at $$x$$ (including the starting point, so $$u(0) = 1$$). Thus $$u(x) = (u(x+1) + u(x-2))/2$$ for $$x \ne 0$$, and you want $$(u(1) + u(-2))/2$$. The recurrence $$u(x) = (u(x+1) + u(x-2))/2$$ has basic solutions $$u(x) = r^x$$ for $$r = 1$$, $$(1- \sqrt{5})/2$$ and $$(1+\sqrt{5})/2$$. Thus for some constants $$a_-, b_-, c_-, a_+, b_+, c_+$$ we should have $$u(x) = \cases{a_- + b_- r_1^x + c_- r_2^x & if x < 0\cr a_+ + b_+ r_1^x + c_+ r_2^x & if x > 0\cr}$$ Now because $$|r_1^x| \to \infty$$ for $$x \to -\infty$$ and $$r_2^x \to \infty$$ for $$x \to +\infty$$, we should have $$b_- = 0$$ and $$c_+ = 0$$. Moreover we should have $$u(x) \to 0$$ for $$x \to -\infty$$, so $$a_- = 0$$. To fit with $$u(0)=1$$ we should have $$c_1 = 1$$. Then $$a_+$$ and $$b_+$$ are determined by $$u(1) = (u(-1) + u(2))/2$$ and $$u(2) = (u(0)+u(3))/2$$, i.e.

\eqalign{a_+ + b_+ r_1 &= (r_2^{-1} + a_+ + b_+ r_1^2)/2 \cr a_+ + b_+ r_1^2 &= (1 + a_+ + b_+ r_1^3)/2 \cr}

whose solutions are \eqalign{a_+ &= \frac{3 \sqrt{5} - 5}{2}\cr b_+ &= \frac{7 - 3 \sqrt{5}}{2}\cr}

That makes your answer $$(r_2^{-1} + a_+ + b_+ r_1)/2 = \frac{9 - 3 \sqrt{5}}{4}$$

• two questions: firstly, I think you used $-X_n$ instead of you $X_n$ in your recursions. Secondly, I don't understand how do you get the recursion relation on $u(x)$. How do you express $u(x)$ with the $X_n$, what means "starting point" here? ($n,X_0$??) Jun 22, 2019 at 6:33
• and another point that I don't understand: how to show that the probability that we want is $1/2 (u(-1)+u(2))? Jun 22, 2019 at 8:07 • I'm pretty sure I didn't make that mistake.$u(x)$is the probability, for a walk starting at$X_0 = x$and making each step$+1$or$-2$with equal probabilities, that$X_n$is ever$0$. The recursion is obtained by "first step analysis": starting at$x \ne 0$, with probabilty$1/2$the first step is$+1$and you are at$x+1$, and with probability$1/2$the first step is$-2$and you are at$x-2$, so$u(x) = (1/2) u(x+1) + (1/2) u(x-2)$. Jun 24, 2019 at 20:29 • Our actual process starts at$0$, but we don't want to count that as "twice as many heads as tails", so we look again at the result of the first step:$(1/2) u(1) + (1/2) u(-2)\$. Jun 24, 2019 at 20:31

So imagine the number of tosses is $$3n$$. Now you have to pick $$2n$$ of them and place Head over there and for every place, the probability of it being head is $$1/2$$. So the probability of having $$2n$$ heads and n tails is $${3n \choose 2n}\frac{1}{2}^{2n}\frac{1}{2}^n$$
$$P(H = 4) = {6 \choose 4}\frac{1}{2}^{4}\frac{1}{2}^2$$