Consecutive Heads [Two Sigma Statistics Interview Question]

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:

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:

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:

Plugging this into the original equation yields:

and after solving we get:

Therefore we would expect 6 flips.