How Long Will You Be Stuck at the Bar?

A marker sits at $0$ on the integer number line, and a fair coin is flipped over and over. Heads moves the marker one step in the positive direction, tails one step in the negative direction. You hold the winning number $-X$ (a negative integer) and your friend holds the winning number $+Y$ (a positive integer). You win if the marker reaches $-X$ first, and your friend wins if it reaches $+Y$ first. How many flips, on average, does a complete game take?

The Riddler, FiveThirtyEight(original post)

Solution

The whole problem turns on one fact about averages: the expected time to finish, written as a function of the marker’s position, bends at a constant rate. That forces it to be a parabola, and two known values pin the parabola down.

Measure position by how far the marker sits to the right of your number $-X$. Call that $n$, so $n$ runs from $0$ (the marker is on $-X$, you have won) to $X+Y$ (the marker is on $+Y$, your friend has won). The game starts at the origin, which is $n=X$. Let $E(n)$ be the expected number of flips still to come from position $n$. The two ends are settled: $$E(0) = 0, \qquad E(X+Y) = 0,$$ because the game is already over there.

For an interior position, one flip happens for certain, and then the marker is equally likely to sit at $n-1$ or $n+1$: $$E(n) = 1 + \tfrac12 E(n-1) + \tfrac12 E(n+1).$$ Rearranging puts the structure on display: $$E(n+1) - 2E(n) + E(n-1) = -2.$$ The left side is the second difference of $E$, the discrete version of a second derivative. A second difference equal to a constant $-2$ means $E$ is a quadratic whose leading coefficient is $-1$: $$E(n) = -n^2 + A\,n + B,$$ for some constants $A$ and $B$. The boundary values fix them. From $E(0)=0$ we get $B=0$. From $E(X+Y)=0$ we get $-(X+Y)^2 + A(X+Y) = 0$, so $A = X+Y$. Hence $$E(n) = -n^2 + (X+Y)\,n = n\,(X+Y-n).$$ This is worth reading aloud: the expected length from position $n$ is the product of the two gaps, the distance $n$ to your barrier and the distance $X+Y-n$ to your friend’s. The game begins at $n=X$, where the gaps are $X$ and $Y$, so $$E(X) = X\,(X+Y-X) = \boxed{X\,Y}.$$ A short game on one side ($X$ small) keeps the whole thing short no matter how far away the other barrier is, which matches the intuition that you almost always drift to the near wall first.

The computation

Play the actual game. Start the marker at $0$, flip a fair coin until it hits $-X$ or $+Y$, count the flips, and average over many games. The mean should land on $X\cdot Y$.

import random
random.seed(0)

def game_length(X, Y):
    pos, flips = 0, 0
    while -X < pos < Y:
        pos += 1 if random.random() < 0.5 else -1
        flips += 1
    return flips

for X, Y in [(3, 4), (5, 7), (2, 9)]:
    trials = 400_000
    mean = sum(game_length(X, Y) for _ in range(trials)) / trials
    print(f"X={X} Y={Y}: simulated={mean:6.3f}  X*Y={X*Y}")
# X=3 Y=4: simulated=11.978  X*Y=12
# X=5 Y=7: simulated=34.955  X*Y=35
# X=2 Y=9: simulated=18.010  X*Y=18