Section 3 Gambler’s ruin

The gambler’s ruin Markov chain
Equations for probability of ruin and expected duration of the game by conditioning on the first step

3.1 Gambler’s ruin Markov chain

Consider the following gambling problem. Alice is gambling against Bob. Alice starts with £$a$ and Bob starts with £$b$. It will be convenient to write $m = a + b$ for the total amount of money, so Bob starts with £$(m-a)$. At each step of the game, both players bet £1; Alice wins £1 off Bob with probability $p$, or Bob wins £1 off Alice with probability $q$. The game continues until one player is out of money (or is “ruined”).

Let $X_n$ denote how much money Alice has after $n$ steps of the game. We can write this as a stochastic process with discrete time $n \in \{0,1,2,\dots\} = \mathbb Z_+$ and discrete state space $\mathcal S = \{0,1,\dots,m\}$. Then $X_0 = a$, and, for $n \geq 0$, we have \[ X_{n+1} = \begin{cases} X_n + 1 & \text{with probability $p$ if $1\leq X_n \leq m-1$,} \\ X_n - 1 & \text{with probability $q$ if $1\leq X_n \leq m-1$,} \\ 0 & \text{if $X_n = 0$,} \\ m & \text{if $X_n = m$.} \end{cases} \] So Alice’s money goes up one with probability $p$ or down one with probability $q$, unless the game is already over with $X_n = 0$ (Alice is ruined) or $X_n = m$ (Alice has won all Bob’s money, so Bob in ruined).

We see that the gambler’s ruin process $(X_n)$ clearly satisfies the Markov property: the next step $X_{n+1}$ depends on where we are now $X_n$, but, given that, does not depend on how we got here.

The gambler’s ruin process is exactly like a simple random walk started from $X_0 = a$ except that we have absorbing barriers and $0$ and $m$, where the random walk stops because one of the players has ruined. (One could also consider random walks with reflecting barriers, that bounce the random walk back into the state space, or mixed barriers that are absorbing or reflecting at random.)

There are two questions about the gambler’s ruin that we’ll try to answer in this section:

What is the probability that the game ends by Alice ruining?
How long does the game last on average?

3.2 Probability of ruin

The gambling game continues until either Alice is ruined ($X_n = 0$) or Bob is ruined ($X_n = m$). A natural question to ask is: What is the probability that the game ends in Alice’s ruin?

Let us write $r_i$ for the probability Alice ends up ruined if she currently has £$i$. Then the probability of ruin for the whole game is $r_a$, since Alice initially starts with £$a$. The probability Bob will end up ruined is $1 - r_a$, since one of the players must lose.

What can we say about $r_i$? Clearly we have $r_0 = 1$, since $X_n = 0$ means that Alice has run out of money and is ruined, and $r_m = 0$, since $X_n = m$ means that Alice has won all the money and Bob is ruined. What about when $1 \leq i \leq m-1$?

The key is to condition on the first step. That is, we can write \[\begin{align*} \mathbb P(\text{ruin}) &= \mathbb P(\text{win first round}) \, \mathbb P(\text{ruin} \mid \text{win first round}) \\ &\qquad{}\quad {}+ \mathbb P(\text{lose first round}) \, \mathbb P(\text{ruin} \mid \text{lose first round}) \\ &= p\,\mathbb P(\text{ruin} \mid \text{win first round}) + q \,\mathbb P(\text{ruin} \mid \text{lose first round}) . \end{align*}\] Here we have conditioned on whether Alice wins or loses the first round. More formally, we have used the law of total probability, which says that if the events $B_1, \dots, B_k$ are disjoint and cover the whole sample space, then \[ \mathbb P(A) = \sum_{i=1}^k \mathbb P(B_i) \, \mathbb P(A \mid B_i) . \] Here, $\{\text{Alice wins the first round}\}$ and $\{\text{Alice loses the first round}\}$ are indeed disjoint events that cover the whole sample space. This idea of “conditioning on the first step” will be the most crucial tool throughout this whole module.

If Alice wins the first round from having £$i$, she now has £$(i+1)$. Her probability of ruin is now $r_{i+1}$, because, by the Markov property, it’s as if the game were starting again with Alice having £$(i+1)$ to start with. The Markov property tells us that it doesn’t matter how Alice got to having £$(i+1)$, it only matters how much she has now. Similarly, if Alice loses the first round, she now has £$(i-1)$, and the ruin probability is $r_{i-1}$. Hence we have \[ r_i = pr_{i+1} + qr_{i-1}. \]

Rearranging, and including the “boundary conditions”, we see that the equation we want to solve is \[ pr_{i+1} - r_i + qr_{i-1} = 0 \qquad \text{subject to} \qquad r_0 = 1,\ r_m = 0. \] This is a linear difference equation – and, because the left-hand side is $0$, we call it a homogeneous linear difference equation.

We will see how to solve this equation in the next lecture. We will see that, if we set $\rho = q/p$, then the ruin probability is given by \[ r_a = \begin{cases} \displaystyle\frac{\rho^a - \rho^m}{1 - \rho^m} & \text{if $\rho \neq 1$,} \\[0.35cm] 1 - \displaystyle\frac{a}{m} & \text{if $\rho = 1$.} \end{cases} \] Note that $\rho = 1$ is the same as the symmetric condition $p = q = \frac12$.

Imagine Alice is not playing against a similar opponent Bob, but rather is up against a large casino. In this case, the casino’s capital £$(m-a)$ is typically much bigger than Alice’s £$a$. We can model this by keeping $a$ fixed taking a limit $m \to \infty$. Typically, the casino has an “edge”, meaning they have a better than $50:50$ chance of winning; this means that $q > p$, so $\rho > 1$. In this case, we see that the ruin probability is \[ \lim_{m \to \infty} r_a = \lim_{m \to \infty} \frac{\rho^a - \rho^m}{1 - \rho^m} = \lim_{m \to \infty} \frac{\rho^a/\rho^m - 1}{1/\rho^m - 1} = \frac{0-1}{0-1} = 1, \] so Alice will be ruined with certainty.

Even with a generous casino that offered an exactly fair game with $p = q = \frac12$, so $\rho = 1$, we would have \[ \lim_{m \to \infty} r_a = \lim_{m \to \infty}\left( 1 - \frac{a}{m} \right) = 1-0 = 1 , \] so, even with this fair game, Alice would still be ruined with certainty.

(The official advice of the University of Leeds module MATH2750 is that you shouldn’t gamble against a casino if you can’t afford to lose.)

3.3 Expected duration of the game

We could also ask for how long we expect the game to last.

We approach this like before. Let $d_i$ be the expected duration of the game from a point when Alice has £$i$. Our boundary conditions are $d_0 = d_m = 0$, because $X_n = 0$ or $X_n = m$ means that the game is over with Alice or Bob ruined. Again, we proceed by conditioning on the first step, so \[\begin{align*} \mathbb E(\text{duration}) &= \mathbb P(\text{win first round}) \, \mathbb E(\text{duration} \mid \text{win first round}) \\ &\qquad{}+ \mathbb P(\text{lose first round}) \, \mathbb E(\text{duration} \mid \text{lose first round}) \\ &= p\,\mathbb E(\text{duration} \mid \text{win first round}) + q \,\mathbb E(\text{duration} \mid \text{lose first round}) . \end{align*}\] More formally, we’ve used another version of the law of total probability, \[ \mathbb E(X) = \sum_{i=1}^k \mathbb P(B_i) \, \mathbb E(X \mid B_i) , \] or, alternatively, the tower law for expectations \[ \mathbb E(X) = \mathbb E_Y \mathbb E (X \mid Y) = \sum_{y} \mathbb P(Y= y)\, E(X \mid Y = y), \] where, in our case, $Y$ was the outcome of the first round.

Now, the expected duration given we win the first round is $1 + d_{i+1}$. This is because the round itself takes $1$ time step, and then, by the Markov property, it’s as if we are starting again from $i+1$. Similarly, the expected duration given we lose the first round is $1 + d_{i-1}$. Thus we have \[ d_i = p(1 + d_{i+1}) + q (1 + d_{i-1}) = 1 + pd_{i+1} + qd_{i-1} . \] Don’t forget the 1 that counts the current round!

Rearranging, and including the boundary conditions, we have another linear difference equation: \[ pd_{i+1} - d_i + qd_{i-1} = -1 \qquad \text{subject to} \qquad d_0 = 0,\ d_m = 0. \] Because the right-hand side, $-1$, is nonzero, we call this an inhomogeneous linear difference equation.

Again, we’ll see how to solve this in the next lecture, and will find that the solution is given by \[ d_a = \begin{cases} {\displaystyle \frac{1}{q-p} \left(a - m\frac{1-\rho^a}{1- \rho^m} \right)} & \text{if $\rho \neq 1$,} \\ \displaystyle a(m-a) & \text{if $\rho = 1$.} \end{cases} \]

Thinking again of playing against the casino, with $q > p$, $\rho > 1$, and $m \to \infty$, we see that the expected duration is \[ \lim_{m\to\infty} d_a = \lim_{m\to\infty} \frac{1}{q-p} \left(a - m\frac{1-\rho^a}{1 - \rho^m} \right) = \frac{1}{q-p} \left(a - 0 \right) = \frac{a}{q-p} , \] since $\rho^m$ grows much quicker than $m$. So Alice ruins with certainty, and it will take time $a/(q-p)$, on average.

In the case of the generous casino, though, with $q = p$, so $\rho = 1$, we have \[ \lim_{m\to\infty} d_a = \lim_{m\to\infty} a(m-a) = \infty . \] So here, Alice will ruin with certainty, but it may take a very long time until the ruin occurs, since the expected duration is infinite.

In the next section, we see how to solve linear difference equations, in order to find the ruin probability and expected duration of the gambler’s ruin.