HH Before HT

Question

Flip a fair coin repeatedly. How many flips do you expect to wait to first see the pattern HH, and how many to first see HT? Most people answer that the two must be equal. They are not.

Accepted Answer

Waiting for HT Track two states: A means no useful progress yet, B means the last flip was an H. Let E_A and E_B be the expected additional flips from each. From A: one flip, then heads (probability frac12) moves you to B, tails keeps you at A. E_A = 1 + tfrac12 E_B + tfrac12 E_A. From B: one flip, then tails finishes, heads leaves you still in B because the new H is a fresh start on the pattern. E_B = 1 + tfrac12 (0) + tfrac12 E_B implies E_B = 2. Substituting, E_A = 1 + 1 + frac12 E_A, so E_A = 4. Waiting for HH Same states, but the failure behaves differently. From B (last flip H), a tail destroys all progress and sends you back to A: E_B = 1 + tfrac12(0) + tfrac12 E_A, qquad E_A = 1 + tfrac12 E_B + tfrac12 E_A. The second gives E_A = 2 + E_B. Substituting into the first: E_B = 1 + frac12(2 + E_B), so E_B = 4 and E_A = 6. E[textflips to HH] = 6, qquad E[textflips to HT] = 4. Why they differ, in one sentence HH overlaps itself and HT does not. When you are one flip into HH and fail, the failing flip is a tail, which is useless and costs you everything. When you are one flip into HT and fail, the failing flip is a head, which is exactly the progress you needed, so you never lose g

HH Before HT

Problem

Your answer

Hints

More Probability to train on