Find expected number of coin tosses to get n consecutive heads.


Let En denote the expected number of tosses to get n consecutive heads. Now if we get one more head after 𝐸n-1, then we have n consecutive heads or if it is a tail the we have to repeat the procedure again. This

En = En-1 + 1 (if it is head)
En = En-1 + 1 + En (if it is tail)

Thus,
En = ½(En + 1) + ½(En-1 + 1 + En)
=> En = 2En-1 + 2

We have the general recurrence relation. Lets define f(n) = En + 2. Since,
En + 2 = 2(En-1 + 2)
=> f(n) = 2 f(n-1)
And f(0) = E0 + 2 = 0

=> f(n) = 2n f(0) = 2n+1

Therefore,
En = f(n) – 2 = 2n+1 – 2
E
n = 2(2n – 1)

For n=5 value of En comes out to be 62. We can also verify this by simulating the problem (code given below).

from random import choice
import numpy as np
import matplotlib.pyplot as plt
from math import floor, ceil

N = 5
N_EXPERIMENTS = 1000
N_TRIALS = 500

sample_estimate = []
for i in range(N_EXPERIMENTS):
	trials = []
	for i in range(N_TRIALS):
		consecutive_heads = 0
		total_trials = 0
		while consecutive_heads < N:
			outcome = choice(['Head', 'Tail'])
			total_trials += 1

			if outcome == 'Head':
				consecutive_heads += 1
			else:
				consecutive_heads = 0
		trials.append(total_trials)
	sample_estimate.append(np.mean(trials))

plt.figure()
plt.hist(sample_estimate, bins=40)

plt.xlabel('Expected number of trials', fontsize=16)
plt.ylabel('Frequency', fontsize=16)

xint = range(int(floor(min(sample_estimate))), int(ceil(max(sample_estimate))+1), 5)

plt.xticks(xint)

plt.show()

Make sure you sign up at Prepleaf for regular quant and puzzle updates. Click here for more exciting puzzles.

Leave a Reply

Your email address will not be published. Required fields are marked *