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