What Is The First Flipper’s Advantage?

You and I take turns flipping a coin, and whoever flips ten heads first wins all the change in the couch. We both want to go first. What is the first flipper’s advantage: what fraction of the time does the first flipper win?

The Riddler, FiveThirtyEight(original post)

Solution

Let $N_A$ be the number of flips the first player needs to reach ten heads, and $N_B$ the number the second player needs. Both are independent and follow the same distribution: the number of flips to collect ten heads, with $\Pr(N=k) = \binom{k-1}{9}2^{-k}$ for $k \ge 10$ (the tenth head on flip $k$, nine of the first $k-1$ being heads).

The first player flips on turns $1,3,5,\dots$, finishing on turn $2N_A - 1$; the second flips on $2,4,6,\dots$, finishing on turn $2N_B$. The first player wins exactly when $2N_A - 1 < 2N_B$, that is, when $N_A \le N_B$. By symmetry $\Pr(N_A < N_B) = \Pr(N_A > N_B)$, so writing $q = \Pr(N_A = N_B)$ for the chance of a tie in flip-counts, $$\Pr(\text{first wins}) = \Pr(N_A \le N_B) = \frac{1 - q}{2} + q = \frac{1 + q}{2}.$$ The tie probability is $q = \sum_{k\ge 10}\Pr(N=k)^2 \approx 0.0658$, so $$\Pr(\text{first wins}) = \frac{1 + 0.0658}{2} \approx \boxed{0.533}.$$ Going first is worth about three and a third percentage points, the whole of it coming from the chance the two would otherwise tie.

The computation

Sum the tie probability from the flip-count distribution, and confirm by playing the alternating game.

from math import comb
import numpy as np
q = sum(comb(k-1, 9)**2 / 4.0**k for k in range(10, 400))   # P(tie in flips)
print((1 + q) / 2)                                           # ~0.533
rng = np.random.default_rng(0); runs = 2_000_000; first = 0
for _ in range(runs):
    a = b = 0
    while True:
        a += rng.random() < 0.5
        if a == 10: first += 1; break          # first player reaches 10 first
        b += rng.random() < 0.5
        if b == 10: break
print(first / runs)                            # ~0.533