Consecutive Heads

What is the expected number of coin flips needed to get two consecutive heads?

This is the same question as problem #12 in the Statistics Chapter of Ace the Data Science Interview!

Let *X* be the number of coin flips needed to obtain two consecutive heads. We then want to solve for E[*X*]. Let H denote a flip that results in heads, and T denote a flip that results in tails. Note that E[*X*] can be written in terms of E[*X*|H] and E[*X*|T], i.e., the expected number of flips needed, conditioned on a flip being either heads or tails respectively.

Conditioning on the first flip, we have:

$E[X] = \frac{1}{2}(1+E[X|H]) + \frac{1}{2}(1+E[X|T])$

Note that E[*X*|T] = E[*X*] since if a tail is flipped, we need to start over in getting two heads in a row.

To solve for E[*X*|H], we can condition it further on the next outcome: either heads (HH) or tails (HT).

Therefore, we have:

$E[X|H] = \frac{1}{2}(1+E[X|HH]) + \frac{1}{2}(1+E[X|HT])$

Note that if the result is HH, then E[*X*|HH] = 0 since the outcome has been achieved, and that E[*X*|HT] = E[*X*] since a tail was flipped, we need to start over in attempting to get two heads in a row. Thus:

$E[X|H] = \frac{1}{2}(1+0) + \frac{1}{2}(1+E[X]) = 1 + \frac{1}{2}E[X]$

Plugging this into the original equation yields:

$E[X] = \frac{1}{2}(1+1+\frac{1}{2}E[X]) + \frac{1}{2}(1+E[X])$

and after solving we get:

$E[X] = 6$

Therefore we would expect 6 flips.