How long until you first see HH?
Asked at Jane Street
A fair coin is flipped repeatedly until the pattern HH first appears.
What is the expected number of flips? And why is the answer for HT different?
Show a hint
Set up states for "how much of the pattern have I matched so far," and write one equation per state.