Expected flips to see two heads in a row
Asked at Jane Street, Two Sigma
You flip a fair coin until you see two heads in a row (HH).
Estimate the expected number of flips by Monte Carlo, then derive the exact answer. Bonus: why is the wait for HT different?
target HH -> ~6 flips
Show a hint
Track how much of the pattern you have so far as a state: "no progress" or "just saw one H." Write one equation per state by conditioning on the next flip.