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):
total_trials = 0
total_trials += 1

else:
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()``````