Definition and Exact Solution of the Gambler's Ruin Problem

This problem is motivated by trying to determine the success or failure of a gambler who goes to a casino with some amount of money initially and wants to leave with some larger amount of money at the end of the evening. For example, the goal of a gambler who comes to the casino with $100 at the beginning of the evening might be to leave the casino with $200. If the gambler walks in and places a bet for the entire amount of money, the problem is easy. The chance of winning will be determined by the game being played. However, if the gambler bets a small amount each time, the problem becomes a little more difficult to analyze.

We will assume that there are two possible outcomes in this problem; after a number of bets (1) the gambler will achieve the goal of winning the desired amount of money (say $200 from $100) and leave the casino, or (2) the gambler can end up with no money. In the second case the gambler is ruined, thus the name Gambler's Ruin for this problem. The goal of the casino, of course, is for the gambler to lose. To simplify the problem a little assume that the gambler will wager one dollar each time the game is played. We could use any unit of money as long as it is the same on each bet. In addition, assume that each time the gambler wagers there is some fixed chance (or probability) that the result will be a win and a fixed chance that the gambler will lose. For example, a gambler may choose to play the same color on a roulette wheel on every bet. In this case, the probability of winning is 18/38. The chance of losing is 20/38.

We could certainly restate this problem in terms of investment strategies or the success or failure of a farmer. Historically, the problem has been stated in terms of the success or failure of a gambler and we will use this approach. In addition, this problem is considered as a classical example of a problem in probability and statistics and appears in a number of standard textbooks on probability and statistics.

With this simple situation to model we must begin to translate the information in the description above into mathematical terms. To begin, we will need to keep track of the sequence of results from each wager. This requires the definition of some variables to keep track of each bet and the total amount of money the gambler has at any time. In the language of statistics these individual results can be defined in terms of random variables.

Definition 1   A random variable $X$ is a real-valued function defined over a sample space.

Let's frame this definition in terms of the problem we are trying to solve. The sample space in our problem is the set of all possible outcomes of an individual playing of the game. In playing colors (red or black) on a roulette wheel we can have any of 38 outcomes when the game is played. In our case the real value assigned to any of the 38 outcomes is defined by whether the gambler wins a dollar or loses the dollar wagered. We can keep track of each win or loss using a sequence of random variables of the form $X_1,X_2,\ldots,X_n$. Note that each variable, $X_i$, is a random variable. The sample space for each of these variables is defined by the the 38 slots on the roulette wheel. The real value assigned to each possibility in the sample space is either 1 or -1. For example, $X_4=-1$ means that the gambler lost a dollar on the fourth time the games was played. Note that there are 18 slots on the wheel associated with the real number 1. The other 20 all get assigned -1.This means there are 18 ways to win and 20 ways to lose. Using a sequence like the one just defined keeps track of the individual bets and the outcomes from each time the game is played.

For our purposes we will assume that the probability of a win or that $X_i=1$ ion the $i^{th}$ play of the game is $p$ and that the probability that the gambler loses a game or that $X_i=-1$ is $q=1-p$. In the roulette example, $p=18/38$ and $q=1-18/38=20/38$. Note that $p>{1\over 2}$ for each individual play of the game favors the gambler and $p<{1\over2}$ favors the casino. We can now start to add things up over the entire process.

To analyze the problem we will assume that the gambler starts with $a$ dollars (say $100) and wants to end up with $c$ dollars (say $200). Note that $a$ and $c$ are integers with $0<a<c$. Both values must be greater than or equal to 0 and if $a>c$ we are already to the goal and would not gamble. Then define the amount of money the gambler has after each eager as $D_n=D(n)$ which can be computed using the formula

$$D_n = a + X_1 + X_2 + \cdots + X_n = a + S_n$$

where $S_n = X_1 + X_2 + \cdots + X_n$ keeps track of the total change in the amount of money at any step in the process. In our example above, if $D_n$ ever hits $200 we stop. If $D_n$ hits 0 we have no choice but to stop the process since we have no more money.

To compute the chance of succeeding in ending up with $c$ dollars we also need to be able to define all possible ways of arriving at $D_n=c$ (success) or $D_n=0$ (ruin). The reason for this is the following. From a simplistic point of view, if we compute the total number of ways of success, $N_s$ and the total number of ways of ruin, $N_r$, we can compute the probability of success as

$$P(success) = {{N_s}\over{N_s+N_r}}$$

As we will see, there are some problems with this simplistic point of view, but we can get an idea of where we are headed.

To keep track of things we will define sets that include the ways a gambler can be successful or ruined in exactly $n$ plays of the game. For example, we will define a set that includes all ways in which the gambler can succeed in exactly 130 plays. Similarly, we will define a set that includes all ways a gambler can be ruined in exactly 130 plays of the game. Define

$$A_{a,n} = \{ D_n = c \ \ , \ \ 0<a+S_k<c \ \ , \ \ k<n \}$$

as the set of events where the gambler wins after exactly $n$ plays and

$$B_{a,n} = \{ D_n = 0 \ \ , \ \ 0<a+S_k<c \ \ , \ \ k<n \}$$

as the set of all possibilities that the gambler loses after exactly $n$ plays. Note that there are many ways to win and lose as well as many ways that the gambler could end up staying forever.

Table 1.1: An example of a sequence that leads to a gambler achieving the desired goal. The pertinent variables are all shown for each play of the game.

$i$	$X_i$	$S_i$	$D(i)$
1	1	1	6
2	1	2	7
3	-1	1	6
4	1	2	7
5	1	3	8

As an example consider the situation where a gambler starts with $5 and wants to end up with $8. The set of ways that a gambler can be successful in exactly 5 plays of the game would include more than one sequence. One suce sequence would be to win, win, lose, win, win. This would mean, the variables we defined above would look like those shown in Table (1.1). It is not hard to image a number of other sequences of 5 plays that would lead to the same result. In addition, there are sequences of many lengths that would lead to success or ruin in the problem. The sets $A_{a,n}$ and $B_{a,n}$ provide a short hand notation for us to keep track of all the sequences.

If we take the union of all the sets $A_{a,n}$ we will get all possible ways of winning and the union of all the sets $B_{a,n}$ will give all possible ways of losing. So define

$$A = \bigcup_{n=1}^\infty A_{a,n}$$

and

$$B = \bigcup_{n=1}^\infty B_{a,n} .$$

If we can figure out the chances of landing in these two sets we will be able to find out the probabilities of the gambler's success or failure.

The next step is to define the probability of being in the sets, $A$ and $B$. We start by letting

$$s_c(a)=P(\bigcup_{n=1}^\infty A_{a,n})=\sum_{n=1}^\infty P(A_{a,n})$$

be the probability of success for the gambler. This is the first time that we have actually defined the probability of the process that we are interested in modeling. The reason we can sum the probabilities of the sets above is that each play is an independent event. We are still left with a fairly daunting task of trying to determine the probability. We need some way to characterize the function $s_c(a)$ that will allow us to answer our question. In the definition of $s_c(a)$, we will let $a$, the amount of money the gambler starts with, and $c$, the desired amount of money, to be two independent variables in the problem.

There are two values of $s_c(a)$ that are easy to obtain. If the gambler starts with no cash, it is impossible to reach the desired amount of money. Setting $a=0$, this means that $s_c(0)=0$. Also if the gambler shows up with $a\geq c$ then it is not necessary to play since the gambler already has the desired amount of money. Setting $a=c$ implies that $s_c(c)=1$. These cases may not seem too interesting, but they are very important in characterizing the problem. These cases are the limiting (or boundary) cases in our simple problem.

Implicit in the definition of the probability $s_c(a)$ is the probability, $p$, of winning an individual play of the game. Using the probabilities, $p$ and $q=1-p$, we can also determine a relationship between different values of $s_c(a)$. In particular, the probability $s_c(a)$ can be related to the two probabilities $s_c(a-1)$ and $s_c(a+1)$ as follows.

$$s_c(a) = p s_c(a+1) + q s_c(a-1).$$

The equation comes from considering what happens on the very first wager if the gambler starts with $a$ dollars. On this turn there is a probability of $p$ that the gambler wins one dollar and then from there onward the probability of success is determined by all sequences starting from $a+1$. The other term in the equation represents the case when the gambler loses a dollar and then the success of the gambler depends on all the sequences that start from $a-1$. The two can be added since the events are all independent.

The result of all this work is the definition of a second order finite difference equation for the function $s_c$. To restate the problem we want to find $s_c(a)$ satisfying the second order difference equation

$$s_c(a) = p s_c(a+1) + q s_c(a-1).$$

and boundary (or limiting) conditions $s_c(0)=0$ and $s_c(c)=1$. There is a very straight forward analogy to solving second order linear ordinary differential equations which will allow us to solve this problem. As we will see, the two limiting cases are an essential part of the solution process. We should also keep in mind that we have finally reduced the description of the simplest of problems to the solution of a well defined mathematical problem.