The New National Pastime: Competitive Coin Flipping

Riddler Express

Two teams of coin flippers each pick a length-two heads/tails sequence and flip their own coin (each team uses its own coin) until that team’s sequence first appears. The team to find its sequence first wins; if both teams find their sequences on the same flip number, they start over and re-flip. Red picks “heads then tails” and Blue picks “heads then heads.” You can bet at even odds on either team. Which team should you back?

The Riddler, FiveThirtyEight, August 31, 2018(original post)

Solution

Set up a joint Markov chain on the two simultaneous flip streams. Let the state $(r, b)$ record each team’s current pattern progress: $r = 0$ means Red has not just seen an H, $r = 1$ means Red’s last flip was H (so a T next finishes HT). Likewise $b = 0, 1$ for Blue and pattern HH. Each second both coins flip independently, giving four outcomes HH, HT, TH, TT of probability $1/4$ each.

The transitions of each team’s progress are: Red’s pattern moves $0 \xrightarrow{H} 1$, $1 \xrightarrow{T} \text{win}$, with any other flip returning to $0$ unless already at $1$. Blue’s pattern moves $0 \xrightarrow{H} 1$, $1 \xrightarrow{H} \text{win}$, $1 \xrightarrow{T} 0$. There are four pre-absorption states $(r, b)$. On a joint flip that finishes both patterns simultaneously, the match restarts, returning the chain to $(0, 0)$. Let $p_{rb}$ denote the probability Red wins from state $(r, b)$. Reading the four joint outcomes off the transitions and multiplying each by $1/4$, $$\begin{aligned} 4 p_{00} &= p_{11} + p_{10} + p_{01} + p_{00}, \\ 4 p_{01} &= p_{10} + p_{00}, \\ 4 p_{10} &= p_{11} + p_{10} + 2, \\ 4 p_{11} &= p_{10} + p_{00} + 1. \end{aligned}$$ A small linear system. Solving gives $p_{00} = \tfrac{5}{8}$, $p_{01} = \tfrac{3}{8}$, $p_{10} = \tfrac{7}{8}$, $p_{11} = \tfrac{5}{8}$ (the analogous system for Blue gives $\tfrac{3}{8}$ at $(0, 0)$, and the two probabilities sum to $1$). $$\boxed{\text{Bet on Red; Red wins with probability } \tfrac{5}{8} = 62.5\%.}$$ Intuitively, after Red flips one head, the very next flip either wins (T) or stays at "just saw an H" (H). Blue, after one head, either wins (H) or resets to "no progress" (T). Red can never lose its progress in one flip; Blue can.

The same answer follows from the joint distribution of the hitting times $T_R$ (first appearance of HT in Red’s stream) and $T_B$ (first appearance of HH in Blue’s stream). A standard count gives $$\begin{aligned} \Pr(T_R = n) &\;=\; \tfrac{n - 1}{2^{n}}, & n &\geq 2, \\ \Pr(T_B = n) &\;=\; \tfrac{f_{n - 3}}{2^{n}}, & n &\geq 3, \end{aligned}$$ with $\Pr(T_B = 2) = 1/4$ and $f_k$ the Fibonacci-like count of length-$k$ binary strings with no two adjacent heads ($f_{-1} = f_0 = 1$, $f_1 = 2$, $f_k = f_{k - 1} + f_{k - 2}$). Summing over $m < n$, $m > n$ and $m = n$ (and restarting on ties) recovers the same $5/8$, as the code below checks.

The computation

Re-encode the race directly. Two independent infinite coin streams, one per team; record the first occurrence of each pattern; restart matches that tie. Repeat a million times and read off the empirical frequency. The exact-arithmetic calculation that produced $5/8$ is also confirmed by summing the joint distribution over a finite truncation.

1. For each match, flip two coins together each step; on each step append the new flip to each team’s running tail and check whether the team’s two-character target appears as a suffix.

2. Once both teams have completed their patterns, compare lengths. On a tie restart the match.

3. Track wins; average over many matches.

import random
from fractions import Fraction

random.seed(0)
HT, HH = "HT", "HH"

def hit(target):
    s = ""
    while True:
        s += random.choice(HT)
        if s.endswith(target):
            return len(s)

def play_once():
    while True:
        tR, tB = hit(HT), hit(HH)
        if tR < tB: return 0  # red wins
        if tR > tB: return 1  # blue wins
        # tie: restart

N = 200_000
red = sum(1 for _ in range(N) if play_once() == 0)
print(f"MC: Red wins {red/N:.4f} (target 0.6250)")

# Exact joint distribution truncation.
def aR(n): return Fraction(n - 1, 2 ** n) if n >= 2 else Fraction(0)
fib = {0: 1, 1: 2}
def f(k):
    if k < 0: return 1
    if k in fib: return fib[k]
    fib[k] = f(k - 1) + f(k - 2)
    return fib[k]
def aB(n):
    if n < 2: return Fraction(0)
    if n == 2: return Fraction(1, 4)
    return Fraction(f(n - 3), 2 ** n)

A = B = T = Fraction(0)
for m in range(2, 200):
    for n in range(2, 200):
        p = aR(m) * aB(n)
        if m < n: A += p
        elif m > n: B += p
        else:     T += p
P_red = A / (A + B)
print(f"exact: P(R<B)={float(A):.6f}  P(B<R)={float(B):.6f}")
print(f"conditional Red win = {P_red} = {float(P_red):.6f}")

The simulator prints a frequency near $0.625$, and the exact summation prints $\tfrac{5}{8}$.

Riddler Classic

Acey and Deucy play Nim, but to dodge the boring first-player-always-wins line they roll three six-sided dice for the starting heap sizes. They then take turns removing counters; whoever takes the last counter wins. Acey moves first. Each player puts up money before the dice are rolled. Deucy puts up a nickel. How much should Acey put up to make the bet fair? Extra credit: how do the odds change in the misère version (the player who takes the last counter loses)? Extra extra credit: what if they roll two dice three times for the initial heap sizes?

The Riddler, FiveThirtyEight, August 31, 2018(original post)

Solution

Normal Nim. Bouton’s theorem (1901) settles three-heap Nim: with heap sizes $a, b, c$, the position is a first-player loss iff the bitwise XOR $a \oplus b \oplus c$ equals zero. Otherwise the first player has a winning move.

For each die from $\{1, 2, 3, 4, 5, 6\}$, the binary representations are at most three bits. The unordered triples in $\{1, \ldots, 6\}^3$ with XOR zero are $$\{1, 2, 3\}, \quad \{1, 4, 5\}, \quad \{2, 4, 6\}, \quad \{3, 5, 6\}.$$ Each unordered triple has all distinct elements, so it contributes $3! = 6$ ordered rolls. That gives $4 \cdot 6 = 24$ first-player losses out of $6^3 = 216$ ordered rolls. The first player (Acey) wins on $216 - 24 = 192$ rolls, so $$\Pr(\text{Acey wins}) \;=\; \tfrac{192}{216} \;=\; \tfrac{8}{9}.$$ For a fair bet, the expected gain of each player must be zero. If Acey stakes $a$ and Deucy stakes $d$ and the winner takes the pot, $$\tfrac{8}{9}(d) - \tfrac{1}{9}(a) \;=\; 0 \quad \Longrightarrow \quad \frac{a}{d} = 8.$$ With Deucy at $5$ cents, Acey should bet $$\boxed{40 \text{ cents}.}$$

Misère variant. In misère Nim, taking the last counter loses. The P-position rule (Bouton, then Sprague-Grundy) is: the first player loses iff

• all heaps have size $\leq 1$ and an even number of heaps have size $1$, or

• some heap has size $\geq 2$ and $a \oplus b \oplus c = 0$.

For three dice, "all heaps $\leq 1$" forces $a = b = c = 1$, which has an odd count of ones, so it is a first-player win under misère. But this position has XOR $1 \neq 0$, so it was already a first-player win under normal Nim. The position $(1, 1, 1)$ has not changed status.

Examine the four XOR-zero triples: each contains an element $\geq 2$, so under misère they remain first-player losses by the second clause. So far the win counts coincide with normal Nim.

What does change? The position $(1, 1, 1)$ is the only "all $\leq 1$" position for three dice. Under normal Nim, $(1, 1, 1)$ is a first-player win (take one heap, leaving $(1, 1, 0)$, an XOR-zero P-position). Under misère, the analysis flips at the endgame: from $(1, 1, 1)$ Acey takes a heap, leaving $(1, 1)$. Deucy takes a heap, leaving $(1)$. Acey is forced to take the last counter and loses. So under misère $(1, 1, 1)$ is a first-player loss.

Misère first-player losses are the same four XOR-zero triples (24 ordered rolls) plus $(1, 1, 1)$ (one ordered roll), totaling 25. Acey wins on $216 - 25 = 191$ rolls. Fair stake ratio is $191 : 25$.

Two dice three times. Each heap is now a sum of two dice, so it takes values in $\{2, \ldots, 12\}$ with the standard non-uniform $2d6$ distribution (counts $1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1$ over $36$ outcomes per heap). The first player loses iff XOR is zero. Enumeration over all $36^3 = 46\,656$ weighted ordered triples (computed below) gives $$\Pr(\text{Acey wins}) \;=\; \tfrac{157}{162}, \qquad \Pr(\text{Deucy wins}) \;=\; \tfrac{5}{162}.$$ The fair ratio is $157 : 5$. Against Deucy’s nickel, $$\boxed{\text{Acey bets } \$1.57.}$$ Heaps are now always at least $2$, so the misère correction (which applied only at the all-ones position) leaves the answer for this variant unchanged.

The computation

Re-encode the game directly: for every dice roll, classify the position by playing the game from that position to a fixed point. Normal and misère outcomes are determined by a depth-first game-tree analysis with memoization; the dice roll distributions are weighted exactly as the dice produce them.

1. Memoise normal_winP1(h) and misere_winP1(h) for sorted tuples h of heap sizes; a position is winning iff some legal move leads to a losing position for the opponent.

2. Iterate over all rolls; weight each by its dice probability; sum the probabilities of first-player loss.

3. Report the fair ratio for each variant.

from functools import lru_cache
from fractions import Fraction

@lru_cache(maxsize=None)
def normal_winP1(h):
    if not any(h): return False
    for i, v in enumerate(h):
        for take in range(1, v + 1):
            new = tuple(sorted(
                v - take if j == i else h[j] for j in range(len(h))
            ))
            if not normal_winP1(new):
                return True
    return False

@lru_cache(maxsize=None)
def misere_winP1(h):
    if not any(h): return True
    for i, v in enumerate(h):
        for take in range(1, v + 1):
            new = tuple(sorted(
                v - take if j == i else h[j] for j in range(len(h))
            ))
            if not misere_winP1(new):
                return True
    return False

# Three dice (1..6), uniform
W_n = L_n = W_m = L_m = 0
for a in range(1, 7):
    for b in range(1, 7):
        for c in range(1, 7):
            h = tuple(sorted((a, b, c)))
            if normal_winP1(h): W_n += 1
            else:               L_n += 1
            if misere_winP1(h): W_m += 1
            else:               L_m += 1
print(f"3 dice normal: P1 wins {W_n}/216 = {Fraction(W_n,216)}")
print(f"3 dice misere: P1 wins {W_m}/216 = {Fraction(W_m,216)}")
print(f"normal ratio {W_n}:{L_n}, fair vs 5c -> {Fraction(W_n,L_n)*5}c")
print(f"misere ratio {W_m}:{L_m}, fair vs 5c -> {Fraction(W_m,L_m)*5}c")

# Two dice three times
dist = {}
for a in range(1, 7):
    for b in range(1, 7):
        dist[a + b] = dist.get(a + b, 0) + 1
W = L = 0
for a, wa in dist.items():
    for b, wb in dist.items():
        for c, wc in dist.items():
            h = tuple(sorted((a, b, c)))
            w = wa * wb * wc
            if normal_winP1(h): W += w
            else:               L += w
print(f"2d6 three times: P1 wins {Fraction(W, W+L)}, "
      f"fair vs 5c -> {Fraction(W,L)*5}c")

The script prints 192/216, 191/216, 157/162, and the three fair stakes against Deucy’s nickel: $40$, $38.2$, and $157$ cents.