# Coin toss puzzle

## Problem

A coin is flipped repeatedly, until a sequence of $$m$$ consecutive heads, or $$n$$ consecutive tails appears. What is the probability that we stop after $$n$$ consecutive tails?

## Solution

Here's a short Python program that gives us a hint that the answer is likely 7/10:

import random
m = 10000
n = 0
for i in range(0, m):
s = ''
while not (s.endswith('HH') or s.endswith('TTT')):
if random.randint(0, 1):
s += 'H'
else:
s += 'T'
if s.endswith('HH'):
n += 1
print(str(n) + '/' + str(m))

So it looks like the answer is 7/10, but what's the reasoning? Let $$H_i$$ denote the probability of "winning" when the sequence ends with $$i$$ heads, and let $$T_j$$ denote the probability of "winning" when the sequence ends with $$j$$ tails. For example, if we tossed HTHHHH, then our probability is given by $$H_4,$$ because the sequence ends with $$4$$ heads. As another example, if we tossed HHHTTTHTT, then our probability is given by $$T_2$$ because the sequence ends with $$2$$ tails.

\begin{align} & H_{m - 1} = \dfrac{1}{2}T_1 \\[1em] & H_{m - 2} = \dfrac{1}{2}H_{m - 1} + \dfrac{1}{2}T_1 = \dfrac{3}{4}T_1 \\[1em] & H_{m - 3} = \dfrac{1}{2}H_{m - 2} + \dfrac{1}{2}T_1 = \dfrac{7}{8}T_1 \\[1em] & \vdots \\[1em] & H_1 = \dfrac{1}{2}H_2 + \dfrac{1}{2}T_1 = \dfrac{2^{m - 1} - 1}{2^{m - 1}}T_1 \end{align}
\begin{align} & T_{n - 1} = \dfrac{1}{2} + \dfrac{1}{2}H_1 \\[1em] & T_{n - 2} = \dfrac{1}{2}T_{n - 1} + \dfrac{1}{2}H_1 = \dfrac{1}{4} + \dfrac{3}{4}H_1 \\[1em] & T_{n - 3} = \dfrac{1}{2}T_{n - 2} + \dfrac{1}{2}H_1 = \dfrac{1}{8} + \dfrac{7}{8}H_1 \\[1em] & \vdots \\[1em] & T_1 = \dfrac{1}{2}T_2 + \dfrac{1}{2}H_1 = \dfrac{1}{2^{n - 1}} + \dfrac{2^{n - 1} - 1}{2^{n - 1}}H_1 \end{align}

Now we know enough to solve for $$H_1$$ and $$T_1.$$

\begin{align} H_1 &= \left(\dfrac{2^{m - 1} - 1}{2^{m - 1}}\right)\left(\dfrac{1}{2^{n - 1}} + \dfrac{2^{n - 1} - 1}{2^{n - 1}}H_1\right) \\[1em] &= \left(\dfrac{2^{m - 1} - 1}{2^{m - 1}}\right)\left[\dfrac{(2^{n - 1} - 1)H_1 + 1}{2^{n - 1}}\right] \\[1em] \end{align} \begin{align} 2^{m + n - 2}H_1 &= (2^{m - 1} - 1)[(2^{n - 1} - 1)H_1 + 1] \\[1em] 2^{m + n - 2}H_1 &= 2^{m + n - 2}H_1 - (2^{m - 1} + 2^{n - 1} - 1)H_1 + (2^{m - 1} - 1) \\[1em] 0 &= -(2^{m - 1} + 2^{n - 1} - 1)H_1 + (2^{m - 1} - 1) \end{align} \begin{align} H_1 &= \dfrac{2^{m - 1} - 1}{2^{m - 1} + 2^{n - 1} - 1} \\[1em] &= \dfrac{2^m - 2}{2^m + 2^n - 2} \end{align}
\begin{align} T_1 &= \dfrac{1}{2^{n - 1}} + \left(\dfrac{2^{n - 1} - 1}{2^{n - 1}}\right)\left(\dfrac{2^m - 2}{2^m + 2^n - 2}\right) \\[1em] &= \dfrac{2^m}{2^m + 2^n - 2} \end{align}

Finally, there's a 50/50 chance our first flip is heads or tails.

\begin{align} p &= \dfrac{1}{2}T_1 + \dfrac{1}{2}H_1 \\[1em] &= \dfrac{1}{2}(T_1 + H_1) \\[1em] &= \left(\dfrac{1}{2}\right)\left(\dfrac{2^m}{2^m + 2^n - 2} + \dfrac{2^m - 2}{2^m + 2^n - 2}\right) \\[1em] &= \dfrac{2^m - 1}{2^m + 2^n - 2} \end{align}

Sources: Physics Forums, AoPS