VLSI DV Interview Puzzles · All levels
Expected Tosses Until First HH
For a fair coin, what is the expected number of tosses until two consecutive heads first appear?
Puzzle
Difficulty: Medium · Puzzle 2 of 6 · Topic: Probability Puzzles
For a fair coin, what is the expected number of tosses until two consecutive heads first appear?
Hint
Define states by suffix memory: start and 'last toss was H'.
Step-by-step solution
diagram
1) Let E be expectation from start, and E_H from state 'last toss was H'.
2) From start: E = 1 + 0.5*E_H + 0.5*E.
3) From E_H: one toss occurs. With prob 0.5 get H and finish, with prob 0.5 get T and return to start.
4) So E_H = 1 + 0.5*0 + 0.5*E = 1 + 0.5E.
5) Rearranging first equation: 0.5E = 1 + 0.5E_H => E = 2 + E_H.
6) Substitute: E = 2 + 1 + 0.5E => 0.5E = 3 => E = 6.Answer
Answer: Expected tosses to first HH are 6.
Why candidates get it wrong
Counting only the HH pattern itself and ignoring restarts after HT.
Interviewer follow-up
What is the expected toss count until first HT?