Gambler's ruin

Problem

A gambler starts with $k$ units of money, where $0 \le k \le N$ for an integer $N \ge 1$. In each round, the gambler wins one unit with probability $p \in (0, 1)$ and loses one unit with probability $q = 1 - p$. The rounds are independent. The game stops when the fortune reaches $0$ (ruin) or $N$ (the target). Find the probability $P_k$ that the gambler reaches $N$ before $0$.

Remarks

The fortune is a random walk on $\{0, 1, \dots, N\}$ that stops at $0$ and $N$. By the law of total probability for the first round, $P_k = p P_{k+1} + q P_{k-1}$ for $0 < k < N$, with $P_0 = 0$ and $P_N = 1$. For a fair game, $p = q = 1/2$, the solution is $P_k = k/N$. For $p \ne q$, the solution is $P_k = \dfrac{1 - (q/p)^k}{1 - (q/p)^N}$. In a fair game against an opponent with unlimited money ($N \to \infty$), the gambler is ruined with probability $1$.

History

An early form of the problem appears in a letter of Blaise Pascal to Pierre de Fermat in 1656.

Explanations

L1 human

A gambler who plays a fair game against a much richer opponent will almost surely lose everything in the end. With $10$ units and a target of $100$ in a fair game, the chance to reach the target is only $10/100 = 0.1$.