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)
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
En = f(n) – 2 = 2n+1 – 2
En = 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()