I found a nice little app/game the other day called Probability Puzzles. Apologies to those who, like me, will now obsess until they are all completed. I'm sure there will be many such people on this site!
Anyway, Puzzle 14 of the Outrageous section contained the following:
When considering an infinite sequence of tosses of a fair coin, how long will it take on average until the pattern H T T H appears.
It's a lovely puzzle.
My methodology involved using
Markov chains (and a few lines on Python).
However, he provided the following hint:
The answer is necessarily larger than 4. A trick for solving it easily by hand is to use martingales. Suppose that at each time $N$ a person arrives and bets 1 dollar on the $N$th roll being H. If they win, they then bet 2 on T; if they win again, 4 on T; and if they win again, 8 on H. They stop betting as soon as they either lose once or win four bets in a row. The cumulative amount won by these betters is a mean-zero martingale, and you can use that fact to solve for the expected amount of time until the first H T T H.
This rings a very faint bell from 20 years ago, but briefly reading up on it did not get me much closer.
- Answer the problem with whatever method you like.
- Answer the problem with the method in the hint for bonus points!
I'm sorry I didn't explicitly state this earlier, but the tick will go to the first answer to both questions!