Don’t Flip Out!

Kyle and Julien each toss their own fair coin, once per turn, at the same time. Kyle wins as soon as his three most recent flips are Tails, Tails, Heads (TTH). Julien wins as soon as his three most recent flips are Tails, Tails, Tails (TTT). If both happen on the same turn, nobody wins and they simply keep flipping, history intact, so either could win a turn or two later. What is the probability that Kyle wins?

The Fiddler, Zach Wissner-Gross, December 15, 2023(original post)

The official solution appeared in the post of December 22, 2023 and gives $45{,}667/71{,}106 \approx 64.2$ percent for the main puzzle, and HTH or THT, each with a winning chance of about $49.6$ percent, for the Extra Credit. Both agree with the answers below.

Solution

The two targets look almost the same, so an answer near one half is tempting. The truth is quite different, and the reason lies in what each player keeps after a near miss.

What matters about each player’s history is only how many tails he has just flipped in a row, counted up to two. If Kyle has a run of two tails, he wins on heads, and on tails he still has a run of two tails, so he is still one flip from winning. If Julien has a run of two tails, he wins on tails, but on heads his run drops to zero and he must start again. That difference is the whole story; the rest is bookkeeping.

So describe the game by the pair $(i, j)$: Kyle’s current run of tails and Julien’s, each $0$, $1$ or $2$. Let $p(i, j)$ be Kyle’s chance of winning from there. Each turn the four combinations of flips each have probability $1/4$.

• When neither run is $2$, nobody can win this turn. Heads resets a run to $0$ and tails lengthens it. For example $$p(0, 0) = \tfrac14\left[p(0,0) + p(0,1) + p(1,0) + p(1,1)\right].$$ The same pattern gives $p(0, 1)$, $p(1, 0)$ and $p(1, 1)$.

• When only Julien’s run is $2$, tails wins for Julien. Kyle’s chances survive only on Julien’s heads: $p(0, 2) = \tfrac14\left[p(0,0) + p(1,0)\right]$ and $p(1, 2) = \tfrac14\left[p(0,0) + p(2,0)\right]$.

• When only Kyle’s run is $2$, heads wins for Kyle, and tails leaves his run at $2$: $p(2, 0) = \tfrac12 + \tfrac14\left[p(2,0) + p(2,1)\right]$ and $p(2, 1) = \tfrac12 + \tfrac14\left[p(2,0) + p(2,2)\right]$.

• When both runs are $2$: two heads win for Kyle, two tails win for Julien, and Kyle’s tails with Julien’s heads lead to $(2, 0)$. Kyle’s heads with Julien’s tails completes both patterns at once. That turn is a tie, Kyle’s run becomes $0$ and Julien’s stays $2$: $p(2, 2) = \tfrac14 + \tfrac14\left[p(2,0) + p(0,2)\right]$.

These are nine linear equations in nine unknowns. Solving them (by elimination, starting from the three equations with $i = 2$) gives

and each value can be checked by substituting it back into its equation. The game starts at $(0, 0)$, so $$\boxed{\ P(\text{Kyle wins}) \;=\; \frac{45667}{71106} \;\approx\; 64.2\%. \ }$$ The bottom row shows the advantage at work. Once Kyle reaches a run of two, he wins about $96$ percent of the time from $(2, 0)$, because his near miss never costs him anything.

The computation

The program plays the game forwards, without the streak bookkeeping. It keeps the exact flip history that matters (each player’s last two flips) and the probability of each such history among games still going. Each turn it spreads every history over the four flip combinations, collects Kyle’s wins, drops Julien’s wins, and lets ties carry on. After $400$ turns the probability of a game still going is below $10^{-40}$.

from collections import Counter
from itertools import product

def kyle_wins(A, B, turns=400):
    games = {("", ""): 1.0}       # last two flips of each
    win = 0.0
    for _ in range(turns):
        nxt = Counter()
        for (a, b), pr in games.items():
            for x, y in product("HT", repeat=2):
                na, nb = (a + x)[-3:], (b + y)[-3:]
                if na == A and nb != B:
                    win += pr / 4              # Kyle wins
                elif nb != B or na == A:   # play on, or tie
                    nxt[(na[-2:], nb[-2:])] += pr / 4
        games = nxt
    return win

print(f"Kyle wins: {kyle_wins('TTH', 'TTT'):.6f}")
print(f"45667/71106 = {45667 / 71106:.6f}")

It prints

Kyle wins: 0.642238
45667/71106 = 0.642238

Extra Credit

The eight three-flip sequences HHH, HHT, HTH, THH, HTT, THT, TTH, TTT are written on slips and put in a hat. Kyle draws one, then Julien draws one of the remaining seven, and they play the same game with those targets. Having looked at his slip, Kyle says “this is about as fair as it could possibly be”. Which slip or slips might he have drawn, and what is his chance of winning at that moment?

Solution

Kyle’s chance, once he knows his slip, is the average of his chances against the seven slips Julien might draw. So we need every head-to-head.

Here the main puzzle’s lesson helps: what decides a match is how each pattern behaves after a near miss, which depends on how the pattern overlaps itself. The eight slips fall into three families.

• HHT, HTT, THH, TTH do not overlap themselves at all: no tail of the pattern matches its own beginning. After one appears, the next appearance must start from scratch.

• HTH and THT overlap themselves in one flip: the final flip can start the next copy (HTHTH contains two).

• HHH and TTT overlap themselves in one or two flips.

Each player flips his own coin, so there is no interaction between the patterns themselves, only between their timings, and two patterns from the same family appear on the same schedule. Swapping heads and tails turns HHT into TTH, HTH into THT and HHH into TTT. Within the non-overlapping family something stronger holds. For any three-flip pattern, the chance that it is completed at a given flip (from the third on) is $1/8$. A non-overlapping pattern’s appearances never share flips, so these chances fix the spacing between appearances completely, and all four patterns run on the same schedule. Two players with the same schedule have equal chances by symmetry. So every match within a family is exactly even, and only three kinds of match remain. The same method as in the main puzzle, a system of equations over the recent flips of each player, gives

The more a pattern overlaps itself, the worse it does. Every pattern turns up once per eight flips in the long run, but a self-overlapping one turns up in clusters with longer gaps between, and its first appearance takes longer on average: $10$ flips for HTH and $14$ for HHH, against $8$ for the others.

Now average over Julien’s seven possible slips. Drawing a non-overlapping slip, Kyle meets three others of his family (even), the two of the middle family ($55.0$ percent) and HHH and TTT ($64.2$ percent): $\tfrac17(3 \cdot 0.5 + 2 \cdot 0.550 + 2 \cdot 0.642) \approx 55.5$ percent. Drawing HHH or TTT, he gets $\tfrac17(0.5 + 4 \cdot 0.358 + 2 \cdot 0.413) \approx 39.4$ percent. Drawing HTH or THT, he meets four non-overlapping slips ($45.0$ percent), his own twin (even) and HHH and TTT ($58.7$ percent): $$\frac17\left(4\left(1 - \tfrac{28675}{52162}\right) + \tfrac12 + 2 \cdot \tfrac{1673}{2850}\right) \;=\; \frac{36901193}{74330850} \;\approx\; 49.6\% .$$ That is the closest of the three to an even game. $$\boxed{\ \text{HTH or THT}, \text{ with a winning chance of about } 49.6\%. \ }$$ If Julien draws with replacement, so that he might match Kyle’s slip (an even game), the average is over eight slips and Kyle’s chance rises to about $49.7$ percent. The answer is the same.

The computation

The simulation from The computation above takes any two targets. Play every slip against the seven others and average each row.

slips = ["".join(t) for t in product("HT", repeat=3)]
for s in slips:
    avg = sum(kyle_wins(s, t) for t in slips if t != s) / 7
    print(s, f"{avg:.4f}")
print(f"36901193/74330850 = {36901193 / 74330850:.4f}")

It prints

HHH 0.3939
HHT 0.5548
HTH 0.4964
HTT 0.5548
THH 0.5548
THT 0.4964
TTH 0.5548
TTT 0.3939
36901193/74330850 = 0.4964