Expected number of coin flips to get THTHTT

Question

Suppose I am flipping a fair coin. What's the expected number of coin flips to get THTHTT?

I know how to do this using a Markov chain approach. However, I end up with a system of six linear equations. I can work through the algebra but it becomes unwieldy. I wonder if there is an easier way, such as through a Martingale approach?

Can I get a hint?

Answer 1

Below i will use $0,1$ instead of $H,T$. Consider the space $\Omega$ of all $0,1$-words, and the $\sigma$-algebra generated by all events $A(w)$, where $A(w)$ is the set of words starting with $w$. We give $A(w)$ the probability $(1/2)$ to the power length of $w$.

Our pattern of interest is: $$ \bbox[yellow]{\qquad101011\qquad} $$ On $\Omega$ we have the a lot of previsible gamblers. Let $w_1w_2w_3\dots$ be a word in $\Omega$.

The gambler $n$ bets on the "letters" $w_nw_{n+1}w_{n+2}w_{n+3}w_{n+4}w_{n+5}\dots$. If the casino is still working. (The gambler wants of course more / longer, but the rules of the game are not making this possible.)

The casino decides to stop when $101011$ occurs for the first time. This is a stopping time $\tau$ on $\Omega$.

Each gambler comes with one € and sets it over and over again, as long as still winning, on results corresponding to our pattern. In its first chance $1$, then $0$, then $1$, then $0$, then $1$, then $1$. (And then something that does not matter any more.)

Each match is rewarded by the double of the last bet amount. This is a fair game. So let us compute the wins of the casino, and of the many gamblers, restricted to $A(w)=A(w'101011)$ for some word $w=w'101011$ that does not contain the pattern $101011$ at an earlier place:

• Casino wins $\Bbb E[\tau|A(w)]$, the length of $w$ in €.

• All the many gamblers, except for the last six, lose their money, since the pattern was never before.

• Gambler $-6$ wins $2^6$ €, here is the superposition:

    ...101011
       101011 bets of gambler -6 :: perfect match
  

• Gambler $-5$ wins $0$ €, here is the superposition:

    ...101011
        10101 bets of gambler -5 :: first 1 loses
  

• Gambler $-4$ wins $0$ €, here is the superposition:

    ...101011
         1010 bets of gambler -4 :: last zero loses
  

• Gambler $-3$ wins $0$ €, here is the superposition:

    ...101011
          101 bets of gambler -3 :: first one loses
  

• Gambler $-2$ wins $0$ €, here is the superposition:

    ...101011
           10 bets of gambler -2 :: last zero loses
  

• Gambler $-1$ wins $2$ €, here is the superposition:

    ...101011
            1 bets of gambler -1 :: the one wins, now the casino closes.
  

Putting all money in a balance, we have, first conditioned to $A(w)$, then after aggregation on all $\Omega$ (since the pattern comes with probability one): $$ \bbox[yellow]{\qquad E[\tau]=64+2=66\ .\qquad} $$

---

Monte-Carlo check:

import random
random.seed('101011')

steps, N = 0, 10**5
for trial in range(N):
    w = ''
    while len(w) < 6 or w[-6:] != '101011':
        w += random.choice('01')
        steps += 1

print(f"Statistical mean this time: {steps} / {N} = {RR(steps/N)}")

And we get:

Statistical mean this time: 6604326 / 100000 = 66.0432600000000