Gambler’s Ruin

This post discusses the gambler’s ruin concept.

Stopping Problems and Boundary Problems

There are two classes of problems we can solve when discussing gambler’s ruin: stopping problems and boundary problems. 

Stopping problems are concerned with the termination of a process, either by ruin or conditionally. They include questions like “What is the probability of ruin?”, “What is the optimal stopping strategy?” etc.

Boundary problems are concerned with cases where the path hits or crosses a predefined value. They include questions like “What is the expected duration of a path before it terminates?”.

Probability of Ruin

Let’s derive the formula for calculating probability of ruin.

Suppose we have two persons, A and B, gambling with an initial total asset of “a” amount (e.g. a = $10). At each step, the bet size is $1 and the game continues until either one of them goes bust.

Let 

p = probability of A winning and 
q = probability of A losing
x = amount of initial capital A has
Q_x = probability of ruin starting from capital x.

If A has capital x today, one time step later, A’s capital will either be x + 1, or x -1. If A has x + 1, his probability of ruin becomes Qx+1. Similarly, if he has x-1, the probability of ruin becomes Qx-1.

Therefore, 

Q_x = pQ_{x+1} + qQ_{x-1}

In other words, the probability of ruin with capital x is the probability of winning this round multiplied by the probability of ruin with capital x+1, plus the probability of losing this round multiplied by the probability of ruin with capital x-1.

If p equals q, There are two solutions to the equation above, either

Q_x = 1 \text{ or } Q_x = \left(\frac{q}{p}\right)^x\text{, where }p \neq q 

We can verify the two solutions by substituting them into the equation and simplifying using laws of indices.

For Q_x = 1

Qx+1 = 1, Qx-1 = 1 (as the probability of ruin is a constant and does not depend on the initial capital).

Therefore, 

1 = p(1) + q(1)
1 = p + q
1 = 1

For Q_x = (q/p)^x

\begin{aligned}
\left(\frac{q}{p}\right)^x &= p\left(\frac{q}{p}\right)^{x+1} + q\left(\frac{q}{p}\right)^{x-1}\\
\left(\frac{q}{p}\right)^x &= p\left(\frac{q^{x+1}}{p^{x+1}}\right) + q\left(\frac{q^{x-1}}{p^{x-1}}\right)\\
\left(\frac{q}{p}\right)^x &= \frac{q^{x+1}}{p^{x}} + \frac{q^{x}}{p^{x-1}}\\
\left(\frac{q}{p}\right)^x &= \frac{q^{x+1}}{p^{x}} + \frac{q^{x}p}{p^{x}}\\
\left(\frac{q}{p}\right)^x &= \frac{q^{x}q + q^{x}p}{p^{x}} \\
\left(\frac{q}{p}\right)^x &= \frac{q^{x}(q + p)}{p^{x}} \\
\left(\frac{q}{p}\right)^x &= \frac{q^{x}}{p^{x}} \\
\left(\frac{q}{p}\right)^x &= \left(\frac{q}{p}\right)^x\text{ (shown)}
\end{aligned}

The generalized solution is given by

Q_x = A + B\left(\frac{q}{p}\right)^x\text{, where A and B are constants}

By imposing the boundary conditions Q0 = 1 and Qa = 0, we can solve for A and B. This gives us

Q_x = \frac{m^a - m^x}{m^a - 1}\text{, where m = }\frac{q}{p}\text{ and p}\neq q

If p equals q,

Q_x = 1 - \frac{x}{a}

Application of the Q_x formula:

Suppose we have a = 100, x = 99, p = 0.4

Substituting these values into the Q_x formula gives us 

Q_x = 0.3333

This shows that even if the odds are against us, if we have an initial capital of $99, there is a higher probability that we will hit the target of $100 before ruin. 

This is provided we have a definite stopping point (i.e. we stop when a = 100). If we play indefinitely, the probability of ruin is 1 as the expected return is negative (since the odds are against us).

Expected Duration of Game

Let D_x = expected duration of game with an initial capital of x.

D_x = pD_{x+1} + qD_{x-1} + 1

We add 1 because the duration increases by 1 when we have one more play of the game. Solving D_x gives us the following formulas:

\begin{aligned}
D_x &= \frac{x}{q-p} - \frac{a}{q-p} \frac{1-(q/p)^x     }{ 1-(q/p)^a      },\;\;\;\;(p\neq q)\\
D_x &= x(a-x),\;\;\;\;(p=q) 
\end{aligned}