2.4 The Gambler’s Ruin Problem

Overview¶

Consider two gamblers with finite resources who repeatedly play the same game against each other. Using the tools of conditional probability, we can calculate the probability that each of the gamblers will eventually lose all of his money to the opponent.

2.4.1 Statement of the Problem¶

Suppose that two gamblers $A$ and $B$ are playing a game against each other. Let $p$ be a given number ($0 < p < 1$), and suppose that on each play of the game, the probability that gambler $A$ will win one dollar from gambler $B$ is $p$ and the probability that gambler $B$ will win one dollar from gambler $A$ is $1 − p$. Suppose also that the initial fortune of gambler $A$ is $i$ dollars and the initial fortune of gambler $B$ is $k − i$ dollars, where $i$ and $k − i$ are given positive integers. Thus, the total fortune of the two gamblers is $k$ dollars. Finally, suppose that the gamblers play the game repeatedly and independently until the fortune of one of them has been reduced to 0 dollars. Another way to think about this problem is that $B$ is a casino and $A$ is a gambler who is determined to quit as soon he wins $k − i$ dollars from the casino or when he goes broke, whichever comes first.

We shall now consider this game from the point of view of gambler $A$. His initial fortune is $i$ dollars and on each play of the game his fortune will either increase by one dollar with a probability of $p$ or decrease by one dollar with a probability of $1 − p$. If $p > 1/2$, the game is favorable to him; if $p < 1/2$, the game is unfavorable to him; and if $p = 1/2$, the game is equally favorable to both gamblers. The game ends either when the fortune of gambler $A$ reaches $k$ dollars, in which case gambler $B$ will have no money left, or when the fortune of gambler $A$ reaches 0 dollars. The problem is to determine the probability that the fortune of gambler $A$ will reach $k$ dollars before it reaches 0 dollars. Because one of the gamblers will have no money left at the end of the game, this problem is called the Gambler’s Ruin problem.

Solution of the Problem¶

We shall continue to assume that the total fortune of the gamblers $A$ and $B$ is $k$ dollars, and we shall let $a_i$ denote the probability that the fortune of gambler $A$ will reach $k$ dollars before it reaches 0 dollars, given that his initial fortune is $i$ dollars. We assume that the game is the same each time it is played and the plays are independent of each other. It follows that, after each play, the Gambler’s Ruin problem essentially starts over with the only change being that the initial fortunes of the two gamblers have changed. In particular, for each $j = 0, \ldots, k$, each time that we observe a sequence of plays that lead to gambler $A$’s fortune being $j$ dollars, the conditional probability, given such a sequence, that gambler $A$ wins is $a_j$. If gambler $A$’s fortune ever reaches 0, then gambler $A$ is ruined, hence $a_0 = 0$. Similarly, if his fortune ever reaches $k$, then gambler $A$ has won, hence $a_k = 1$. We shall now determine the value of $a_i$ for $i = 1, \ldots, k-1$.

Let $A_1$ denote the event that gambler $A$ wins one dollar on the first play of the game, let $B_1$ denote the event that gambler $A$ loses one dollar on the first play of the game, and let $W$ denote the event that the fortune of gambler $A$ ultimately reaches $k$ dollars before it reaches 0 dollars. Then

$$

$$ {#eq-2-4-1}

Since the initial fortune of gambler $A$ is $i$ dollars ($i = 1, \ldots, k-1$), then $\Pr(W) = a_i$. Furthermore, if gambler $A$ wins one dollar on the first play of the game, then his fortune becomes $i + 1$ dollars and the conditional probability $\Pr(W \mid A_1)$ that his fortune will ultimately reach $k$ dollars is therefore $a_{i+1}$. If $A$ loses one dollar on the first play of the game, then his fortune becomes $i − 1$ dollars and the conditional probability $\Pr(W \mid B_1)$ that his fortune will ultimately reach $k$ dollars is therefore $a_{i−1}. Hence, by eq-2-4-1,

{#eq-2-4-2}

We shall let $i = 1, \ldots, k-1$ in eq-2-4-2. Then, since $a_0 = 0$ and $a_k = 1$, we obtain the following $k − 1$ equations:

$$

$$ {#eq-2-4-3}

If the value of $a_i$ on the left side of the $i$th equation is rewritten in the form $p a_i + (1 − p)a_i$ and some elementary algebra is performed, then these $k − 1$ equations can be rewritten as follows:

$$

$$ {#eq-2-4-4}

By equating the sum of the left sides of these $k − 1$ equations with the sum of the right sides, we obtain the relation

{#eq-2-4-5}

Solution for a Fair Game: Suppose first that $p = 1/2$. Then $(1 − p)/p = 1$, and it follows from eq-2-4-5 that $1 − a_1 = (k − 1)a_1$, from which $a_1= 1/k$. In turn, it follows from the first equation in eq-2-4-4 that $a_2 = 2/k$, it follows from the second equation in eq-2-4-4 that $a_3 = 3/k$, and so on. In this way, we obtain the following complete solution when $p = 1/2$:

{#eq-2-4-6}

Solution for an Unfair Game: Suppose now that $p \neq 1/2$. Then eq-2-4-5 can be rewritten in the form

{#eq-2-4-7}

Hence,

{#eq-2-4-8}

Each of the other values of $a_i$ for $i = 2, \ldots, k-1$ can now be determined in turn from the equations in eq-2-4-4. In this way, we obtain the following complete solution:

{#eq-2-4-9}

Summary¶

We considered a gambler and an opponent who each start with finite amounts of money. The two then play a sequence of games against each other until one of them runs out of money. We were able to calculate the probability that each of them would be the first to run out as a function of the probability of winning the game and of how much money each has at the start.

Exercises¶