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

Let *E*_{n} 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

*E*_{n}* = E*_{n-1}* + 1* (if it is head)*E*_{n}* = E*_{n-1}* + 1 + E*_{n} (if it is tail)

Thus,*E*_{n}* = ½(E*_{n}* + 1) + ½(E*_{n-1}* + 1 + E*_{n}*)*

=> *E*_{n}* = 2E*_{n-1}* + 2*

We have the general recurrence relation. Lets define *f(n) = E*_{n}* + 2.* Since,*E _{n} + 2 = 2(E_{n-1} + 2)*

=>

*f(n) = 2 f(n-1)*

And

*f(0) = E*

_{0}

*+ 2 = 0*

=> *f(n) = 2*^{n}* f(0) = 2*^{n+1}

Therefore,*E*_{n}* = f(n) – 2 = 2*^{n+1}* – 2 E*

_{n}

**= 2(2**^{n}

**– 1)**For *n=5* value of *E*_{n} 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.