probability - Expected Number of Tosses Until H,T,T,H

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.

So:

1. Answer the problem with whatever method you like.


2. 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!

Answer

Proof along the lines in the hint:

First of all, note that the net winnings of all the bettors up to a given time is, as claimed, a martingale, because its change at any future time is a sum of mean-0 random variables and therefore itself has mean 0.

A single given bettor's net winnings will be 0 (before they start), -1 (if they ever lose, and for ever thereafter), +1 (if they have just seen H), +3 (if they have just seen HT), +7 (if they have just seen HTT), or +15 (if they have just seen HTTH, and for ever thereafter).

Suppose the first HTTH happens when its final H is on turn $n$. Total winnings at this point are -1 from the first $n-4$ bettors, +15 from the one who started with the first H, -1 from the next, -1 from the next, and +1 from the last: so a total of $18-n$.

Hence the expected value of the total winnings when HTTH first occurs is $18-t$ where $t$ is the the expected turn number when that happens.

But now we can apply the optional stopping theorem, which says that the expected value of a martingale at a stopping time equals its initial expected value. (The first time when we get HTTH is certainly a stopping time.) The initial expected value is 0 (again, all the individual bets have expectation 0) and therefore $18-t=0$. Thus $t=18$. (In particular, Carl's calculation is correct, not that that was in doubt.)

Fun further exercise: consider applying the same reasoning to other sequences besides HTTH and figure out the general formula for the expected time to see them.