Ruin Probabilities
The gambler’s ruin problem is one of the oldest and most celebrated problems in probability theory, with roots going back to the correspondence between Pascal and Fermat in the seventeenth century. In its simplest form, a gambler bets repeatedly on fair coin flips and faces two questions: what is the probability of accumulating A dollars before losing B dollars, and how long should she expect to play before one outcome or the other occurs? Despite the elementary setup, these questions lead naturally to some of the most powerful tools in probability: martingales, harmonic functions, and the theory of stopping times.
In these notes, which follow Steele (2001) closely, we analyze both questions in the setting of a simple symmetric random walk. We derive closed-form answers using second-order linear difference equations, a technique that recurs throughout stochastic processes and mathematical finance. The analysis reveals a striking result: starting from zero, the probability of winning A dollars before losing B dollars is exactly B/(A + B), and the expected duration of the game is AB. Both answers carry an elegant symmetry and intuition well beyond the gambling context, appearing naturally in models of sequential testing, insurance risk, and the pricing of barrier options.
A Simple Random Walk
A simple random walk models the wealth of a gambler betting on fair coin flips. To start, let \{X_{i}\}_{i=1}^{\infty} be a sequence of independent random variables, each taking values 1 or -1 with equal probability \frac{1}{2}. Therefore, at each turn the gambler can either win one dollar or lose one dollar.
By construction, the sequence \{X_{i}\} is iid with mean \operatorname{E}(X_{i}) = 0.5 \times 1 + 0.5 (-1) = 0 and variance \operatorname{V}(X_{i}) = 0.5 \times (1 - 0)^{2} + 0.5 \times (-1 - 0)^{2} = 1.
Let S_{0} be the initial wealth of the gambler. For n \geq 1, define S_{n} = S_{0} + \sum_{i=1}^{n} X_{i}. We will assume that the wealth may become negative, which requires the gambler to honor any potential losses.
Define \tau as the first time n > 0 when S_{n} reaches either A or -B: \tau = \min\{n > 0 : S_{n} = A \text{ or } S_{n} = -B\}. At the random time \tau, S_\tau is either A or -B, and we seek to compute the probability of the gambler winning A dollars before losing B dollars, that is \operatorname{P}(S_{\tau} = A \mid S_{0} = 0). Also, it is almost natural to ask how long do we need to wait for the gambler to either win A dollars or to lose B dollars. We will denote this expectation by \operatorname{E}(\tau \mid S_{0} = 0).
Behavior of \tau
To solve these problems, we need first to make sure that the questions have an answer! That is, how do we know for sure that the gambler’s net winnings will eventually reach A or -B?
From any position strictly between -B and A, the gambler is at most A + B - 1 steps below A, so A + B consecutive wins end the game.1 Split time into blocks of A + B steps, and let E_{k} be the event that the gambler wins every step of block k + 1, that is, steps k (A + B) + 1 through (k + 1)(A + B). The events E_{k} involve different coin flips, so they are independent, and p = \operatorname{P}(E_{k}) = \left(\frac{1}{2}\right)^{A + B} > 0. If the game is still running after n blocks, none of the first n blocks was a winning streak. Therefore, \operatorname{P}(\tau > n (A + B)) \leq \operatorname{P}\left(\cap_{k = 0}^{n - 1} E_{k}^{C}\right) = (1 - p)^{n} \xrightarrow[n \rightarrow \infty]{} 0. Since \operatorname{P}(\tau = \infty) \leq \operatorname{P}(\tau > n (A + B)) for all n, we see that \operatorname{P}(\tau = \infty) = 0. In words, it must take a finite time for the wealth of the gambler to reach A or -B.
1 The number A + B, the distance between the two barriers, is not tight. Any streak length of at least A + B - 1 would do, because the argument only needs a fixed length that finishes the game from every position, so that each block has the same positive chance of ending it.
The same bound shows that the expected duration is finite. Writing \tau = \sum_{m = 0}^{\infty} \mathbf{1}_{\{\tau > m\}} and taking expectations gives \operatorname{E}(\tau) = \sum_{m = 0}^{\infty} \operatorname{P}(\tau > m). The probability \operatorname{P}(\tau > m) decreases with m, so each block of A + B consecutive terms starting at m = n (A + B) adds at most (A + B) \operatorname{P}(\tau > n (A + B)), and \operatorname{E}(\tau) \leq (A + B) \sum_{n = 0}^{\infty} (1 - p)^{n} = \frac{A + B}{p} < \infty. The bound is far from sharp, since we will find that \operatorname{E}(\tau) = AB when S_{0} = 0, but it shows that the question has an answer. The same argument applied to \operatorname{E}(\tau^{d}) = \sum_{m = 0}^{\infty} \left((m + 1)^{d} - m^{d}\right) \operatorname{P}(\tau > m), a polynomial times a geometrically decaying tail, shows that every moment of \tau is finite. We compile the results in the following result.
Solving for the Probability
In this section we solve for \operatorname{P}(S_{\tau} = A \mid S_{0} = 0). To do so, we solve the more general problem for all starting values K. Since the gambler can keep playing without any explicit time limit, the problem depends only on the current wealth level rather than on time. In other words, the only relevant state variable is the wealth level.
Let’s write f(K) = \operatorname{P}(S_{\tau} = A \mid S_{0} = K). In words, f(K) denotes the probability of reaching A before -B if we start with a wealth level -B \leq K \leq A. Clearly, f(-B) = 0 since if we start at S_{0} = - B the game is over. Also, f(A) = 1 since if we start at S_{0} = A we have reached our objective. These are our boundary conditions that will allow us to solve for f(K).
Now, we need to get an equation. We note that if we start with S_{0} = K and we win, then our wealth increases to K + 1 and we start all over as if time is back at zero but our initial wealth is K + 1. Similarly, if we start with S_{0} = K and we lose, then our wealth decreases to K - 1 and the problem is the same with an initial wealth of K - 1. Thus, it must be the case that f(K) = \frac{1}{2} f(K - 1) + \frac{1}{2} f(K + 1). \tag{1}
Equation (1) is a second-order linear difference equation in the wealth level K. Equations like this are not a special feature of gambling. They appear whenever two conditions hold. First, the quantity we want depends only on the current state of the system, here the wealth level, and not on how the system got there. Second, the system moves from its current state to nearby states with known probabilities. Conditioning on the first move then expresses the value at each state as an average of the values at the neighboring states, which is a difference equation in the state.2
2 The same argument prices an option in a binomial tree, where today’s value is the discounted risk-neutral average of the two values one period ahead. In continuous time the neighboring states become infinitesimally close and difference equations become differential equations, such as the Black-Scholes equation in the notes on derivatives pricing. The general result is the Feynman-Kac formula: an expected discounted payoff solves a partial differential equation whose coefficients are the drift and volatility of the process.
Solutions to equations like (1) are typically of the form f(K) = z^{K} where z is a real or complex number. If we try with f(K) = z^{K} in equation (1) we find z^{K} = \frac{1}{2} z^{K - 1} + \frac{1}{2} z^{K + 1}, so that z^{2} - 2 z + 1 = (z - 1)^{2} = 0. The only solution to the second order polynomial is 1, so we know that a constant is a solution. But there should be two linearly independent solutions, as is expected of a second-order linear difference equation. When there is a repeated root z = 1, a second independent solution is K \cdot 1^K = K, which we can verify directly: substituting f(K) = K into (1) gives K = \frac{1}{2}(K - 1) + \frac{1}{2}(K + 1), which holds trivially. The general solution to equation (1) is then f(K) = \alpha + \beta K. \tag{2}
To solve for \alpha and \beta in equation (2) we just use the fact that f(-B) = 0 and f(A) = 1, so that \begin{aligned} \alpha - \beta B & = 0, \\ \alpha + \beta A & = 1. \end{aligned} This implies that \alpha = \frac{B}{A + B} and \beta = \frac{1}{A + B} so that f(K) = \frac{B + K}{A + B}.
We can finally conclude that \operatorname{P}(S_{\tau} = A \mid S_{0} = 0) = f(0) = \frac{B}{A + B}. Therefore, the probability of making $10 before losing $10 is just 10 / 20 = 1 / 2, and the probability of making $10 before losing $5 is 5 / 15 = 1 / 3.
Example 1 A trader buys a stock whose price moves up or down by $1 each period with probability 1/2, and follows a common rule: sell with a profit once the price has risen by $10 (a take-profit order), or sell with a loss once it has fallen by $5 (a stop-loss order). With A = 10 and B = 5, the probability that the trade ends with the profit is \operatorname{P}(S_{\tau} = A) = \frac{5}{10 + 5} = \frac{1}{3}. The trade loses $5 two times out of three and gains $10 one time out of three, so its expected profit is 10 \times \frac{1}{3} - 5 \times \frac{2}{3} = 0.
The result in Example 1 holds for any A and B, since A \frac{B}{A + B} - B \frac{A}{A + B} = 0. The choice of the two exit levels changes the shape of the outcome, frequent small losses against occasional large gains or the reverse, but not its expected value. The notes on discrete-time martingales show that this is a general fact: no rule for when to stop can turn a fair game into a favorable one.
Solving for the Expectation
We now want to solve for how long does it take on average to either win $A or lose $B. That is, we want to compute \operatorname{E}(\tau \mid S_{0} = 0). For this, like before we define g(K) = \operatorname{E}(\tau \mid S_{0} = K), and note that g(-B) = g(A) = 0, since the game has already ended at the boundary, so the expected additional time to stop is zero. We can then work the recursion as follows. If we are currently at S_{0} = K, and we play once more, the expected time to reach the target or lose it all has increased by one. If we win it’s the same problem with either one extra or one less unit of wealth, each happening with probability 1 / 2. Thus, g(K) = 1 + \frac{1}{2} g(K - 1) + \frac{1}{2} g(K + 1). \tag{3}
To solve for (3), we already have the homogeneous solution computed earlier. We can find a particular solution by trying \gamma K^{2} which is the next power of K. Therefore, \gamma K^{2} = 1 + \frac{\gamma}{2} (K - 1)^{2} + \frac{\gamma}{2} (K + 1)^{2}, or K^{2} = \frac{1}{\gamma} + \frac{1}{2} (K^{2} - 2 K + 1) + \frac{1}{2} (K^{2} + 2 K + 1). Thus, we find that 1 / \gamma + 1 = 0 or \gamma = - 1. The general solution to (3) is then g(K) = \alpha + \beta K - K^{2}. \tag{4} We determine the constants \alpha and \beta in (4) using \begin{aligned} \alpha - \beta B - B^{2} & = 0, \\ \alpha + \beta A - A^{2} & = 0. \end{aligned} We find that \beta (A + B) = A^{2} - B^{2} = (A + B) (A - B), so \beta = A - B and \alpha = (A - B) B + B^{2} = AB.
Thus, we conclude that g(K) = AB + (A - B) K - K^{2}, and \operatorname{E}(\tau \mid S_{0} = 0) = g(0) = AB. A quick check: with A = B = 1 the game always ends after one flip, and indeed AB = 1.
Example 2 A gambler bets $1 per round and stops after winning or losing $10, so A = B = 10. The game lasts AB = 100 rounds on average. If the gambler instead stops after winning or losing $100, the expected duration is 100 \times 100 = 10{,}000 rounds. Multiplying both barriers by 10 multiplies the expected duration by 100. Suppose instead that the gambler has already won $5 when we start counting, so K = 5. The probability of reaching $10 is then f(5) = (10 + 5)/20 = 0.75, and the expected remaining duration is g(5) = 100 + 0 \times 5 - 25 = 75 rounds.
The expected duration grows with the square of the distance to the barriers. A random walk needs about n^{2} steps to travel a distance n, because after m steps its typical distance from the start is of order \sqrt{m}, as shown in the notes on probability basics. This is the same scaling that turns a random walk into a Brownian motion.
A Biased Coin
In most games the odds are not fair. Suppose each bet is won with probability p and lost with probability q = 1 - p, with p \neq q. The argument that led to (1) now gives f(K) = p f(K + 1) + q f(K - 1). Trying f(K) = z^{K} as before leads to p z^{2} - z + q = 0, whose roots are z = 1 and z = q / p, as in the notes on generating functions. The roots are now distinct, so the general solution is f(K) = \alpha + \beta (q / p)^{K}. Imposing f(-B) = 0 and f(A) = 1 gives f(K) = \frac{(q / p)^{K + B} - 1}{(q / p)^{A + B} - 1}. \tag{5} As p \to 1/2, the ratio q / p approaches one and (5) converges to (K + B) / (A + B), the fair-coin answer.
Example 3 A bet on red in American roulette wins with probability p = 18/38 = 0.4737, so q / p = 20 / 18 = 1.1111. A gambler who bets $1 at a time and stops after winning or losing $10 reaches the target with probability f(0) = \frac{(q / p)^{10} - 1}{(q / p)^{20} - 1} = 0.2585, compared with 0.5 for a fair coin. With barriers at $100, the probability falls to 2.7e-05.
A small disadvantage on each bet becomes a large one over a long game, because the gambler keeps betting until one of the barriers is reached. The longer the game lasts, the more the house edge accumulates. The notes on Brownian motion find the same structure in continuous time, where a Brownian motion with drift reaches a barrier with a probability in which e^{-2 \mu / \sigma^{2}} plays the role of q / p.
Checking by Simulation
The formulas \operatorname{P}(S_{\tau} = A) = B / (A + B) and \operatorname{E}(\tau) = A B are easy to check by simulation. Figure 1 shows five games of the trader in Example 1, with A = 10 and B = 5. In 20,000 simulated games, the trade ended with the profit in a fraction 0.335 of the games, compared with 1/3, and lasted 49.84 periods on average, compared with AB = 50.
