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

Question

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 1

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.

Answer 2

This will require

$18$ tosses on average

since

Let $a$ denote the number of coin tosses it takes to get HTTH. Starting from no progress, no correct, either, we get T or H. If we get H we will progress, while if the get T we stay with no progress. Both ways, we have tossed the coin once. In the next, we have H. If we get H we stay with progress one correct or we proceed to next stage two correct. We have tossed one coin either way. The expected number of tosses from this state (conditioned probability, if you will) until we have HTTH is $b$. Following, we have HT so either we get H and go back to one correct or to three correct. Expected tosses from here is $c$. Finally, we get to either four correct or no correct. Expectation of tosses starting from HTT to HTTH is $d$. $$\begin{matrix}a = \frac{1}{2}a + \frac{1}{2}b +1 \\ b = \frac{1}{2}b + \frac{1}{2}c+1 \\c = \frac{1}{2}b + \frac{1}{2}d+1 \\ d = \frac{1}{2}a + 1 \\ \end{matrix}$$

Here is a graphical representation

Here is a simulation

 import random

 E = 0
 for j in range(0, 20000):
    s  = ""
    i = 0
    while True:
        i += 1
        s += random.choice(["0", "1"])
        if s[-4:] == "0110":
            break
    E += i

 print 1.0*E/20000

A more combinatorial proof is possible by counting the possible sequences ...HTTH so that HTTH is not a substring, but it is not as simple as a probabilistic one. I did actually try this, by defining the sequence $a(n)$ as the number of sequences not containing HTTH. Then, we can compute $\sum_i^\infty \mathbb{P}(\{H,T\}^i \text{ends with $HTTH$}|X=i) \cdot \mathbb{P}(X=i)$, in which the first probability term can be computed from $a(n)$... it is a bit involved (and thus not very interesting) and it turns out it yields the same expression as a Markov chain.