Written by Colin+ in algebra, big in finland, probability, puzzles.

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."

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.

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.

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!

Pingback: Kolikkopeli | Opettaja H:n pulmakulma