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?
Define states by suffix memory: start and 'last toss was H'.
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: Expected tosses to first HH are 6.
Checked by running a model of the rule in a Python model. A computational check: solving the pattern-matching Markov chain exactly with fractions gives 6 tosses for HH and 4 for HT.
Reusing the answer 4 from HT-style waits. After H then T the HH progress is lost and you restart from 'start'; that restart is what makes HH (6) slower than HT (4).
What is the expected toss count until first HT? Model answer: 4. After the first H you only need a T: expected 2 more tosses with no restart (a repeated H keeps you in the 'seen H' state). E = 2 (to the first H) + 2 = 4, versus 6 for HH.
I set up two states: the start, with expectation E, and the state where the last toss was a head, with expectation E-H. From the start, one toss takes me to the head state half the time, so E equals one plus half E-H plus half E. From the head state, a head finishes and a tail sends me all the way back to the start, so E-H equals one plus half E. Solving gives E equal to 6. The trap is quoting 4, which is the answer for head then tail, where a tail after a head does not undo your progress.