Qm
BrainteasersJane StreetOptiver

Waiting for heads-tails versus heads-heads

probabilityexpectationpatternsmarkov-chains

You flip a fair coin repeatedly.

  1. On average, how many flips until you first see heads immediately followed by tails (the pattern HT)?
  2. On average, how many flips until you first see heads immediately followed by heads (HH)?
  3. Both patterns have probability 1/4 on any given pair of flips. Why are the waiting times different?
Show a hint

After a heads, if the next flip is tails, HT is complete. After a heads, if the next flip is tails, the hunt for HH has to start again from nothing. Write the expected times with a small recursion.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

First-Step AnalysisThe Hat-Check Problem and Expected Fixed PointsWhy HHH Takes Longer to Appear Than HHTThe Indicator-Variable TrickPenney's Game and Non-Transitive Patterns

Related questions

The country where every family wants a boyThe expected length of the middle pieceThe expected length of the shorter pieceHow many random numbers until the total passes one?The monkey who rolls again on a six
All questions →