Gambler's Ruin

Player M has $1 and player N has $2. Each game transfers $1 from the loser to the winner. M is the stronger player and wins any single game with probability $\tfrac{2}{3}$ . They play until one of them is broke. What is the probability that M ends up with all the money?

Reveal solutionHide solution

#Set up the walk

Track M's fortune. It starts at 1, moves up a dollar when M wins a game and down a dollar when M loses, and stops the moment it hits 0 (M is broke) or 3 (M has swept the table). That is a random walk on $\{0,1,2,3\}$ with absorbing ends, stepping up with probability $p = \tfrac{2}{3}$ and down with $q = \tfrac{1}{3}$ .

M starts on 1 with two dollars between her and a clean sweep. Each game pushes her fortune up one with probability 2/3 and down one with 1/3, until it sticks at 0 or 3.

#The transition matrix

Index the four states by M's fortune. Reading the moves straight off the walk, the one-step transition matrix $P = (p_{ij})$ is

P = \begin{pmatrix} 1 & 0 & 0 & 0\\[2pt] \tfrac{1}{3} & 0 & \tfrac{2}{3} & 0\\[2pt] 0 & \tfrac{1}{3} & 0 & \tfrac{2}{3}\\[2pt] 0 & 0 & 0 & 1 \end{pmatrix}, \tag{1}

with rows and columns ordered $0,1,2,3$ . Rows $0$ and $3$ carry a lone $1$ on the diagonal, the signature of an absorbing state. Each interior row sends M down a dollar with $\tfrac{1}{3}$ and up a dollar with $\tfrac{2}{3}$ .

#Solve the absorption equations

Let $a_i = \PP(\text{reach }3 \mid \text{start at }i)$ , the chance M sweeps the table from fortune $i$ . The absorbing rows pin $a_0 = 0$ and $a_3 = 1$ , and every interior state is the matrix-weighted average of where it lands next,

a_i = \sum_{j} p_{ij}\,a_j. \tag{2}

The two interior rows of $P$ spell that out,

a_1 = \tfrac{1}{3}a_0 + \tfrac{2}{3}a_2 = \tfrac{2}{3}a_2, \qquad a_2 = \tfrac{1}{3}a_1 + \tfrac{2}{3}a_3 = \tfrac{1}{3}a_1 + \tfrac{2}{3}. \tag{3}

Substituting the first into the second gives $a_2 = \tfrac{2}{3} + \tfrac{2}{9}a_2$ , so $a_2 = \tfrac{6}{7}$ and $a_1 = \tfrac{4}{7}$ .

#The closed form agrees

For a biased walk with ratio $r = q/p$ the absorption probability has a clean form. Here $r = \tfrac{1/3}{2/3} = \tfrac{1}{2}$ , and starting at $i$ with the win state at $N$ ,

a_i = \frac{1 - r^{i}}{1 - r^{N}} = \frac{1 - \tfrac{1}{2}}{1 - \tfrac{1}{8}} = \frac{\tfrac{1}{2}}{\tfrac{7}{8}} = \frac{4}{7}. \tag{4}

#Read it off

\PP(\text{M wins}) = \frac{4}{7} \approx 0.571. \tag{5}

M's edge in skill more than covers her smaller stake. A fair player holding one dollar of three would win only $\tfrac{1}{3}$ of the time; the $\tfrac{2}{3}$ win rate per game lifts that to $\tfrac{4}{7}$ , just past an even chance despite starting behind.