Can You Win The Token Game?

You have one token, and I have two tokens. Naturally, we both crave more tokens, so we play a game of skill over a number of rounds, in which the winner of each round steals one token from the loser. The game ends when one of us is out of tokens, and that person loses. Suppose you are better than me and win each round two-thirds of the time. What is your probability of winning the game?

The Riddler, FiveThirtyEight(original post)

Solution

There are three tokens in all, and your pile performs a random walk on $0,1,2,3$: each round it rises by one with probability $p = \tfrac23$ and falls by one with probability $q = \tfrac13$. You start at $1$ and win if you reach $3$ before $0$. This is the classic gambler’s ruin.

Let $w_i$ be your chance of winning from $i$ tokens, so $w_0 = 0$, $w_3 = 1$, and $w_i = p\,w_{i+1} + q\,w_{i-1}$. The standard solution is $$w_i = \frac{1 - (q/p)^i}{1 - (q/p)^3}, \qquad \frac{q}{p} = \frac{1/3}{2/3} = \frac12.$$ Starting from one token, $$w_1 = \frac{1 - \tfrac12}{1 - \tfrac18} = \frac{1/2}{7/8} = \boxed{\tfrac47} \approx 57.1\%.$$ Being the stronger player almost makes up for starting a token behind, but not quite past even odds.

The computation

Play the game: from your one token against my two, transfer a token each round (you take one with probability $\tfrac23$, lose one with probability $\tfrac13$) until someone hits zero, and record how often you finish with all three.

import numpy as np
rng = np.random.default_rng(0)
runs = 2_000_000
wins = 0
for _ in range(runs):
    you = 1                          # I hold the other 2 of the 3 tokens
    while 0 < you < 3:
        you += 1 if rng.random() < 2/3 else -1
    wins += (you == 3)
print(wins / runs)                   # ~0.5714 = 4/7