Waiting for a run of k heads

Question

Flip a fair coin until you get k heads in a row. Show that the expected number of flips is 2^{k+1} - 2, and give the values for k = 1, 2, 3.

Accepted Answer

Let Ek be the expected number of flips to get a run of k heads. Build the run one head at a time. Suppose you have already achieved a run of k-1 heads (which took E{k-1} flips on average). Now flip once more: - With probability 	frac12 it is heads, completing the run of k. Total cost of this extra step: 1. - With probability 	frac12 it is tails, which destroys the whole run. You have spent one flip and must start the run of k over from scratch, an additional Ek expected flips. So Ek = E{k-1} + 1 + 	frac12\cdot 0 + 	frac12\, Ek. Solving, 	frac12 Ek = E{k-1} + 1, i.e. Ek = 2E{k-1} + 2. Sta…

Waiting for a run of k heads

Your answer

More Probability questions