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.

Steele, J. Michael. 2001. Stochastic Calculus and Financial Applications. Vol. 45. Applications of Mathematics. Springer.

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.¹ 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.

¹ 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.

WarningStopping Time of the Random Walk

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}. For n \geq 1, define S_{n} = S_{0} + \sum_{i=1}^{n} X_{i}, where -B < S_{0} < A, and A and B are two positive integers. 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\}. We then have that \operatorname{P}(\tau = \infty) = 0 and \operatorname{E}(\tau^{d}) < \infty for any integer d \geq 1.

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.²

² 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.

Figure 1: The figure plots five simulated games of the random walk with barriers at A = 10 and -B = -5. Each game stops the first time the walk reaches one of the dashed barriers.

Practice Problems

Problem 1 A trader buys a stock at $50. The price moves up or down by $1 each period with probability 1/2, and the trader sells as soon as it reaches $56 or $47.

1. Compute the probability that the trade ends at $56 and the expected duration of the trade.
2. Show that g(K) = (A - K)(K + B). Some periods later the price is $52. Compute the probability that the trade ends at $56 and its expected remaining duration. Why is the remaining duration longer than the expected duration at the start?
3. Show that \operatorname{E}(S_{\tau} \mid S_{0} = K) = K for every K. What is the expected selling price, given the current price?

Solution

1. Measured from the purchase price, A = 6 and B = 3, so the probability is f(0) = 3 / 9 = 1/3 and the expected duration is g(0) = AB = 18 periods.
2. Expanding, (A - K)(K + B) = AB + (A - B) K - K^{2}, which is g(K). At $52, K = 2, so f(2) = (3 + 2) / 9 = 0.556 and g(2) = (6 - 2)(2 + 3) = 20 periods. The expected duration is a parabola in K with its maximum at the midpoint K = (A - B)/2 = 1.5, a price of $51.50, where the walk is farthest from both barriers. At $50 the stop-loss is only $3 away, while at $52 the nearest barrier is $4 away.
3. Using f(K) = (B + K)/(A + B), \operatorname{E}(S_{\tau} \mid S_{0} = K) = A \frac{B + K}{A + B} - B \frac{A - K}{A + B} = \frac{(A + B) K}{A + B} = K. The expected selling price is the current price, $52 when the price is $52. The exit rule changes how the trade can end, not its expected value.

Problem 2 A gambler has $10 and needs $20 by the end of the night. The gambler bets on red in American roulette, which wins with probability p = 18/38, and stakes the same amount on every round: $1, $2, $5, or $10.

1. Show that when A = B, (5) gives f(0) = \frac{1}{1 + (q / p)^{B}}.
2. Compute the probability of reaching $20 for each stake.
3. Which stake would the gambler choose if the coin were fair? Explain why bold play wins in an unfair game.

Solution

1. With r = q / p and A = B, f(0) = \frac{r^{B} - 1}{r^{2 B} - 1} = \frac{r^{B} - 1}{(r^{B} - 1)(r^{B} + 1)} = \frac{1}{1 + r^{B}}.

2. A stake of s dollars makes each barrier 10 / s units away, so B = 10 / s, and r = 20 / 18 = 1.111.

   Stake	B	(q / p)^{B}	f(0)
   $1	10	2.868	0.2585
   $2	5	1.694	0.3713
   $5	2	1.235	0.4475
   $10	1	1.111	0.4737

3. With a fair coin f(0) = 1/2 for every stake, so the choice does not matter. In roulette each dollar bet loses 1/19 of a dollar on average, and small stakes mean many rounds, so the house edge applies to a much larger total amount wagered. Final wealth is either $0 or $20, so the expected loss is 10 - 20 f(0): $4.83 with $1 stakes against $0.53 with a single $10 bet.

Problem 3 A stock price moves up or down by h dollars every \Delta units of time with probability 1/2, where h = \sigma \sqrt{\Delta}, so the variance of the price change over one unit of time is \sigma^{2}. A trader sells with a profit once the price has risen by a dollars, or with a loss once it has fallen by b dollars, where a and b are multiples of h.

1. Show that the probability of selling with the profit is b / (a + b), and that the expected time until the sale is ab / \sigma^{2} units of time. Neither depends on h.
2. The price change over a trading day of 6.5 hours has variance \sigma^{2} = 4 dollars squared. Compute the probability of the profit and the expected time to the sale when a = 1 and b = 0.5.
3. What happens to the expected number of price changes before the sale as h \to 0?

Solution

1. Over one unit of time there are 1 / \Delta moves, each with variance h^{2}, so the variance is h^{2} / \Delta = \sigma^{2}. In units of h, the barriers are A = a / h and B = b / h, so the probability of the profit is B / (A + B) = b / (a + b). The expected number of moves is AB = ab / h^{2}, each lasting \Delta, so the expected time is ab \Delta / h^{2} = ab / \sigma^{2}.
2. The probability is 0.5 / 1.5 = 1/3, and the expected time is 0.5 / 4 = 0.125 trading days, or about 49 minutes.
3. The expected number of moves ab / h^{2} grows without bound, while the expected time stays at ab / \sigma^{2}. In the limit the price moves infinitely often over any interval of time, by infinitesimal amounts. This limit is a Brownian motion, studied in the notes on Brownian motion.

Problem 4 (★) In many games a round can end in a tie, or push, in which no money changes hands. Suppose each round is won with probability p, lost with probability q, and pushed with probability r = 1 - p - q, where p, q > 0.

1. Show that f(K) = p f(K + 1) + q f(K - 1) + r f(K). Conclude that the probability of reaching A before -B is the same as in a game without pushes in which each round is won with probability p / (p + q).
2. Let p = q. Show that the expected duration is g(K) = \frac{(A - K)(K + B)}{1 - r}.
3. Explain the factor 1 / (1 - r) using the geometric distribution, and compute \operatorname{E}(\tau \mid S_{0} = 0) for A = B = 10 and r = 0.1.

Solution

1. Conditioning on the first round, wealth moves to K + 1, K - 1, or stays at K, which gives the equation. Moving r f(K) to the left side and dividing by 1 - r = p + q, f(K) = \frac{p}{p + q} f(K + 1) + \frac{q}{p + q} f(K - 1), which is the equation of a game without pushes and winning probability p / (p + q), with the same boundary conditions.
2. Conditioning on the first round, g(K) = 1 + p g(K + 1) + q g(K - 1) + r g(K). With p = q = (1 - r)/2, this becomes g(K) = \frac{1}{1 - r} + \frac{1}{2} g(K + 1) + \frac{1}{2} g(K - 1). The function h(K) = (1 - r) g(K) satisfies (3) with h(-B) = h(A) = 0, so h(K) = AB + (A - B) K - K^{2} = (A - K)(K + B), and dividing by 1 - r gives g(K).
3. The number of rounds until one that is not a push has the geometric distribution with success probability 1 - r and mean 1 / (1 - r). Each move of the walk therefore takes 1 / (1 - r) rounds on average, and the walk needs AB moves on average. With A = B = 10 and r = 0.1, \operatorname{E}(\tau) = 100 / 0.9 = 111 rounds.

Problem 5 (★) Let A = B = 2 and S_{0} = 0.

1. Explain why \tau is even, and show that \operatorname{P}(\tau = 2 k) = 2^{-k} for k = 1, 2, \ldots. Hint: look at the walk every two steps.
2. Compute \operatorname{E}(\tau) and \operatorname{V}(\tau), and check the first against AB.
3. Show that the probability generating function of \tau is G_{\tau}(z) = \frac{z^{2}}{2 - z^{2}}.
4. Compare the exact tail probability \operatorname{P}(\tau > 4 n) with the bound (1 - p)^{n} from the notes, where p = (1/2)^{A + B}. Compare also \operatorname{E}(\tau) with the bound (A + B) / p.

Solution

1. After an odd number of steps the walk is at an odd position, so it cannot be at 2 or -2. After two steps the walk is at 2 or -2 with probability 1/2, and back at 0 with probability 1/2. In the second case the game starts afresh, because later flips are independent of the first two. Each pair of steps therefore ends the game with probability 1/2, independently of the other pairs, so \tau / 2 has the geometric distribution with success probability 1/2 and \operatorname{P}(\tau = 2 k) = (1/2)^{k - 1} (1/2) = 2^{-k}.
2. A geometric variable with success probability 1/2 has mean 2 and variance (1 - 1/2)/(1/2)^{2} = 2. Therefore \operatorname{E}(\tau) = 2 \times 2 = 4 = AB and \operatorname{V}(\tau) = 4 \times 2 = 8.
3. G_{\tau}(z) = \sum_{k = 1}^{\infty} 2^{-k} z^{2 k} = \frac{z^{2}/2}{1 - z^{2}/2} = \frac{z^{2}}{2 - z^{2}} for |z| < \sqrt{2}. As a check, G_{\tau}(1) = 1 and G_{\tau}'(z) = 4 z / (2 - z^{2})^{2}, so G_{\tau}'(1) = 4.
4. \operatorname{P}(\tau > 4 n) = \operatorname{P}(\tau / 2 > 2 n) = 2^{-2 n} = (1/4)^{n}, while the bound is (15/16)^{n}. For n = 5 the exact probability is 0.001 and the bound is 0.724. The bound on the mean is 4 / (1/16) = 64, against the exact 4. The argument in the notes only needs each block to have some fixed positive chance of ending the game, and it gives that up to get a proof that works for every A and B.

Problem 6 (★) A gambler with B dollars plays against a casino with unlimited funds, so the game stops only when the gambler is ruined. Let S_{0} = 0 and \tau_{B} = \min\{n > 0 : S_{n} = -B\}.

1. For a fair coin, let A \to \infty in \operatorname{P}(S_{\tau} = A) = B / (A + B) to show that ruin is certain. Explain why \tau_{B} \geq \tau for every A, and conclude that \operatorname{E}(\tau_{B}) = \infty.
2. An insurer starts with a surplus of B units. Each period the surplus rises by one unit with probability p = 0.55 and falls by one unit with probability q = 0.45. Let A \to \infty in (5) to show that the insurer is ruined with probability (q / p)^{B}.
3. Compute the ruin probability for B = 10, and the smallest surplus B that keeps it below 1%.

Solution

1. The probability of losing B before winning A is A / (A + B), which tends to one as A \to \infty. These events grow with A, and their union is the event that the gambler is ever ruined, since a path that reaches -B stays below some finite level before doing so. Continuity of probability gives \operatorname{P}(\tau_{B} < \infty) = 1. Reaching -B ends the game with two barriers too, so on every path that game ends no later, \tau_{B} \geq \tau, and \operatorname{E}(\tau_{B}) \geq \operatorname{E}(\tau) = AB for every A. Therefore \operatorname{E}(\tau_{B}) = \infty. Ruin is certain, but many games last so long that the expected wait is infinite.
2. Let r = q / p < 1. From K = 0, (5) gives the probability of reaching A first, f(0) = \frac{r^{B} - 1}{r^{A + B} - 1} \xrightarrow[A \rightarrow \infty]{} \frac{r^{B} - 1}{-1} = 1 - r^{B}, and the same argument as in the first part shows that the probability of ever being ruined is r^{B} = (q / p)^{B}.
3. With q / p = 9 / 11 = 0.818, the ruin probability for B = 10 is 0.818^{10} = 0.134. It falls below 1% when B \geq \ln(0.01) / \ln(9/11) = 22.95, so the insurer needs B = 23 units, for a ruin probability of 0.0099. Each extra unit of surplus multiplies the ruin probability by q / p, so it decays exponentially in the capital. The notes on Poisson processes find the same exponential decay for an insurer whose claims arrive at random times.

Problem 7 (★★) Let p \neq q and g(K) = \operatorname{E}(\tau \mid S_{0} = K).

1. Show that g(K) = 1 + p g(K + 1) + q g(K - 1), and that K / (q - p) is a particular solution of this equation.
2. Show that g(K) = \frac{(K + B) - (A + B) f(K)}{q - p}, where f(K) is the probability in (5).
3. The gambler of Example 3 bets $1 on red until winning or losing $10. Compute the expected number of bets and compare it with the fair game.
4. Show that \operatorname{E}(S_{\tau} \mid S_{0} = 0) = (p - q) g(0), and interpret this equation for the roulette player.

Solution

1. The first equation follows from conditioning on the first bet, as in (3). Trying g(K) = c K gives c K = 1 + p c (K + 1) + q c (K - 1) = 1 + c K + c (p - q), so c = 1 / (q - p).
2. The general solution is \alpha + \beta (q / p)^{K} + K / (q - p). The proposed g has this form, because f(K) is a combination of 1 and (q / p)^{K}. It also satisfies the boundary conditions: g(-B) = 0 because f(-B) = 0, and g(A) = \frac{(A + B) - (A + B)}{q - p} = 0 because f(A) = 1.
3. With A = B = 10, f(0) = 0.2585 and q - p = 2/38 = 1/19, so g(0) = 19 \left(10 - 20 \times 0.2585\right) = 19 \times 4.83 = 91.8 bets, compared with AB = 100 for a fair coin. The drift pushes the walk toward the lower barrier, so the game ends a little sooner.
4. Using the second part, (p - q) g(0) = (A + B) f(0) - B = A f(0) - B (1 - f(0)) = \operatorname{E}(S_{\tau} \mid S_{0} = 0). For the roulette player both sides equal -4.83 dollars. The expected loss is the house edge of 1/19 dollar per bet times the expected number of bets.

Problem 8 (★★) Let S_{0} = 0 and let A \geq 1 be an integer.

1. For a fair coin, condition on the first step to show that the probability that the walk reaches A before it returns to 0 is 1 / (2 A).
2. Conclude that a fair walk returns to 0 with probability one.
3. For a biased coin with p > q, show that the probability that the walk never returns to 0 is p - q. Hint: after an up step, use (5) with barriers at 0 and A and let A \to \infty. After a down step, the drift pushes the walk back up.

Solution

1. If the first step is down, the walk must pass through 0 before it can reach A. If the first step is up, the walk starts afresh at 1 with barriers at 0 and A, and reaches A first with probability (B + K)/(A + B) with B = 0 and K = 1, which is 1 / A. The probability is \frac{1}{2} \times \frac{1}{A} = \frac{1}{2 A}.
2. A walk that never returns to 0 must reach A before returning, for every A, because it cannot stay between 0 and A forever. Therefore the probability of never returning is at most 1 / (2 A) for every A, so it is zero.
3. With r = q / p < 1, barriers at 0 and A mean B = 0 in (5), so from K = 1 the probability of reaching A before 0 is (r - 1)/(r^{A} - 1), which tends to 1 - r = (p - q)/p as A \to \infty. From -1, the walk reaches 0 before -B with probability (r^{B - 1} - 1)/(r^{B} - 1), from (5) with the walk shifted up by one, and this tends to one as B \to \infty. Therefore the probability of never returning is p \frac{p - q}{p} + q \times 0 = p - q. With p = 0.55, the walk returns to its starting point with probability 0.9. By symmetry, the probability of returning is 1 - |p - q| for every p.