Zeke and Monty play a game. They repeatedly toss a coin until either the sequence tail-tail-head (TTH) or the sequence tail-head-head (THH) appears. If TTH shows up first, Zeke wins; if THH shows up first, Monty wins. What is the probability that Zeke wins?

My first reaction to this question was, “It’s 50-50, right? It has to be 50-50.” But then a moment’s pause: “If it was 50-50, you wouldn’t be asking.”

Of course it isn’t 50-50

If you were to play the game, or simulate it, you’d find that TTH shows up first - on average - about two-thirds of the time. But that’s weird! Surely TTH and THH are equally likely to show up?

Evidently not. I’ve got a heuristic explanation of why not and a more algebraic explanation, both of which I’m quite fond of.

Heuristically

At any given point in the game, the only relevant information is the result of the last two coin tosses - and it’s pretty self-evident that you have equal chances of the last two results being either HH, HT, TH or TT.

  • If you’re in situation TT, Zeke must win. The next toss is either an H (in which case Zeke wins) or a T (in which case we’ve not moved); in either case, Zeke wins.
  • If you’re in situation TH, the next toss is either an H (in which case Monty wins) or a T (in which case we’re in situation HT, where neither player has an obvious advantage.)

Looking at the two situations from which the game can be won, Zeke always wins from his situation, and Monty only wins half the time, so it’s reasonable to conclude that Zeke has a 2-in-3 chance overall.

Algebraically

There’s something a little unsatisfactory and hand-wavy about that, though. It’s true, but it feels somehow off.

Let’s do a little more analysis. Let’s denote $p_{xy}$ being the probability of Zeke winning from situation XY.

  • If we’re in situation HH, we can move to situation HT or remain in HH, so $p_{HH}= \frac{1}{2} p_{HH} + \frac{1}{2} p_{HT}$ [1].
  • If we’re in situation HT, we can move to situation TT or to TH, so $p_{HT}= \frac{1}{2} p_{TT} + \frac{1}{2} p_{TH}$ [2].
  • If we’re in situation TH, we can move to situation THH (which is a win for Monty) or to HT, so $p_{TH}= \frac{1}{2} (0) + \frac{1}{2} p_{HT}$ [3].
  • If we’re in situation TT, we can move to situation TTH (which is a win for Zeke) or to TT, so $p_{TT}= \frac{1}{2} (1) + \frac{1}{2} p_{TT}$ [4].

Four equations in four unknowns! Bring it.

Equations [1] and [4] are the simplest. The first resolves to $p_{HH}=p_{HT}$, which makes sense; if you throw two heads in a row, the only different place to go next is HT. The second resolves to $p_{TT}=1$, which agrees with our heuristic approach earlier.

Looking at [3], we have $p_{TH}= \frac{1}{2} p_{HT}$, so $2p_{TH} = p_{HT}$. We can substitute that into (3): $2p_{TH}= \frac{1}{2} + \frac{1}{2} p_{TH}$. Rearranging gives $p_{TH} = \frac{1}{3}$, and in turn that $p_{HT}=\frac{2}{3}$. $p_{HH} = \frac{2}{3}$ as well.

Given that the probabilities of the first two tosses being HH, HT, TH and TT are each $\frac{1}{4}$, the probability of Zeke winning overall is $\frac{1}{4}\left(p_{HH}+p_{HT}+p_{TH}+p_{TT}\right) = \frac{1}{4}\left( \frac{2}{3} + \frac{2}{3} + \frac{1}{3} + 1 \right) = \frac{2}{3}$.

If you know of a better, especially a more intuitive, argument for the answer, I’d love to hear it!