Вопрос по метрикам
Two players repeatedly toss a fair coin. One waits for HH, the other waits for HT. Who finishes faster on average and how would you reason about it?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
HT has smaller expected waiting time than HH. HH has expected waiting time 6 tosses because an H followed by T partially resets progress; HT has expected waiting time 4 tosses.
Полный разбор
The patterns are not equally fast even though both have probability 1/4 on any fixed pair. Overlapping matters. HH overlaps with itself: after seeing H you are one step toward HH, but if the next toss is T you lose that progress. HT also starts with H, but after H then T it completes immediately.
Use states. For HH, let E0 be expected tosses from no useful suffix and E1 after seeing H. E0 = 1 + 0.5 E1 + 0.5 E0, because T keeps you at E0 and H moves to E1. E1 = 1 + 0.5*0 + 0.5 E0, because H finishes and T resets. Solving gives E0 = 6.
For HT, E0 = 1 + 0.5 E1 + 0.5 E0 and E1 = 1 + 0.5 E1 + 0.5*0, because H keeps suffix H and T finishes. Solving gives E1 = 2 and E0 = 4. Therefore the HT player wins faster on average.
Теория
Pattern waiting times depend on autocorrelation/overlap structure, not just the probability of the pattern in a fixed-length window.
Типичные ошибки
- Assume both patterns have the same expected time because both have probability 1/4.
- Forget that after HH fails with HT, the final H/T state differs depending on the pattern.
- Try to enumerate only the first two tosses.