Can You Even the Odds?

You (player $A$) and a friend (player $B$) take turns rolling a die, and the first to roll a $5$ wins. Plain alternation $AB\,AB\,AB\dots$ favours $A$. To even things out, you use the snake order, reversing within each pair of turns: $AB\,BA\,AB\,BA\dots$. With this order, what is the probability that $A$ wins?

The Fiddler, Zach Wissner-Gross, July 26, 2024(original post)

Solution

Number the rolls $1,2,3,\dots$ ; roll $k$ is the first $5$ with probability $\bigl(\tfrac56\bigr)^{k-1}\tfrac16$, and whoever owns that roll wins. So $A$’s win probability is $\tfrac16\sum_{k\in A}\bigl(\tfrac56\bigr)^{k-1}$, summed over the rolls $A$ takes. The snake order $AB\,BA\,AB\,BA$ hands $A$ the rolls $1,4,5,8,9,\dots$, the positions $4m+1$ and $4m+4$. Summing those two geometric series, $$P(A)=\frac16\left[\frac{1+(5/6)^3}{1-(5/6)^4}\right]=\frac16\cdot\frac{341/216}{671/1296}=\frac{341}{671}=\frac{31}{61},$$ so $A$ wins with probability $$\boxed{\tfrac{31}{61}}\approx50.82\%.$$ Plain alternation gives $A$ the odd rolls and probability $\tfrac{6}{11}\approx54.5\%$, so the snake nearly halves the first-mover edge.

The computation

Assign each roll to its player under the snake rule and add up the chance the first $5$ lands there: the sum collapses to $\tfrac{31}{61}$.

from fractions import Fraction as F
q, p = F(5, 6), F(1, 6)
def turn(k):                                       # 0-indexed roll -> player, snake order
    rnd, pos = k // 2, k % 2
    return ('A', 'B')[pos] if rnd % 2 == 0 else ('B', 'A')[pos]
PA = p * sum(q ** k for k in range(4000) if turn(k) == 'A')
print(PA.limit_denominator(1000))                  # 31/61

Extra Credit

Now take turns by the Thue–Morse sequence, complementing the whole history each round: $A\,B\,BA\,BAAB\,BAABABBA\dots$. What is $A$’s win probability?

Solution

The Thue–Morse order gives roll $k$ (counting from $0$) to $A$ exactly when $k$ has an even number of $1$s in binary. With $s(k)$ that bit-count, the win probability uses the classic product identity $\sum_k(-1)^{s(k)}q^k=\prod_{j\ge0}\bigl(1-q^{2^j}\bigr)$: $$P(A)=\frac12+\frac{1}{12}\prod_{j\ge0}\left(1-\left(\tfrac56\right)^{2^{\,j}}\right)\approx \boxed{0.5016.}$$ The Thue–Morse order is famous as the fairest simple alternation rule, and it pulls $A$’s advantage down to about a sixth of a percent, far below the snake’s $0.8\%$.

The computation

Sum the first-$5$ probability over the rolls the Thue–Morse rule gives $A$ (those with an even binary digit-sum); it lands just above one half.

PA_tm = p * sum(q ** k for k in range(4000) if bin(k).count('1') % 2 == 0)
print(float(PA_tm))                                # 0.50159...