# A martingale solution to gambler’s ruin

In the last post, I gave a simple but tedious proof of the gambler’s ruin problem by first principles. Here is a shorter proof, using martingales. I split the proof of fair games and biased game

#### Fair Game

First consider the case when the probability of winning is 1/2. Let $X_t$ denote the gambler’s fortune at time $t$.  Then $X_t$ is a martingale because

$\displaystyle E[X_{t+1}|X_t] = \frac 12 (X_t + 1) + \frac 12 (X_t - 1)$

Let $\tau$ denote the stopping time when the process stops. Then, by optimal stopping theorem, we have

$E[X_\tau] = E[X_0]$

Thus,

$P_N(n) \cdot N + (1 - P_N(n)) \cdot 0 = n$

and hence

$\displaystyle P_N(n) = \frac nN$

To find the expected number of plays, we use an alternate representation of the problem. For that matter, let $Z_t$ denote the winnings of the gambler at time $t$. Then

$X_t = X_1 + (Z_1 + \cdots + Z_t)$

Since $Z_t$‘s are i.i.d., Wald’s equation can be used to find the﻿stopping time. As $E[Z_t] = 0$, we use the second Wald’s equation

$\displaystyle E\big[ \sum_{t=1}^\tau Z_t - \tau E[Z_t] \big] = E[\tau] \mathop{\hbox{var}}(Z_t)$

Observe that $\mathop{\hbox{var}}(Z_t) = 1$. Then,

$\displaystyle \begin{array}{rl} E[\tau] &{}= E[(X_t - X_1)^2] \\ &{}= P_N(n) (N-n)^2 + (1-P_N(n)) n^2 \\ &{}= \frac nN(N-n)^2 + \frac{N-n}{N}n^2 \\ &{}= n(N-n) \frac{N-n+n}{N} \\ &{} = n(N-n)\end{array}$

#### Biased Game

Now suppose that the probability of winning $p \neq 1/2$. The tricky part in this case is to construct the martingale. Let $\lambda = (1-p)/p$ and $f(x) = \lambda^x$. Then $\{f(X_t)\}$ is a martingale. In particular

$E[f(X_{t+1} | f(X_t)] = p \lambda^{X_t + 1} + (1-p) \lambda^{X_t - 1} = \lambda^X_t = f(X_t)$

Let $\tau$ be the stopping time when the game stops. Then, by optional stopping theorem

$E[f(X_\tau)] = E[X_1]$

So

$P_N(n) f(N) + (1 - P_N(n))f(0) = f(n)$

which simplifies to

$\displaystyle P_N(n) = \frac{ 1- f(n)}{1 - f(N)} = \frac{ 1 - \lambda^n}{1 - \lambda^N}$

The expected stopping time can be computed using Wald’s first equation. Define $Z_t$ as before. Then,

$\displaystyle E[\sum_{t=1}^\tau Z_t] = E[\tau] E[Z_t]$

Note that

$\displaystyle E[Z_t] = p - (1-p) = p(1-\lambda) = \frac { 1 - \lambda}{1 + \lambda}$

Thus,

$\displaystyle E[\tau] = \frac{1 + \lambda}{1-\lambda} [ n - N P_N(n)] = \frac{(1+\lambda)}{(1-\lambda)}\left[ n - N \frac{1 - \lambda^n}{1 - \lambda^N} \right]$

Ah. Much cleaner proof than last time. Now, I can go back to work.

## 2 thoughts on “A martingale solution to gambler’s ruin”

1. Are there are any solutions on a generalized gambler’s ruin problem where there are finite number of win or loss outcomes? Thank you!

2. Hi Sir, thanks for the writing! This post come first when i search gambler’s ruin + martingale in google. It feels good to read through it. To show my appreciation, i would like to point out some misprints suspected.

(a) optional stopping theorem in fair game
optimal stopping theorem <– optional stopping theorem

(b) before using second Wald’s equation:
the﻿stopping time <– the﻿ stopping time

(c) when using second Wald’s equation:
E\left[\sum^{\tau}_{t=1}Z_t – \tau E[Z_t] \right] <– E\left[ (\sum^{\tau}_{t=1}Z_t – \tau E[Z_t])^2 \right]

(d) inside first displayed equation under biased game:
\lambda^X_t <– \lambda^{X_t}

(e) when applying optional stopping theorem in biased game:
E[f(X_\tau)] = E[X_1] <– E[f(X_\tau)] = E[f(X_1)]

(f) the final displayed equation
E\left[\tau\right] = \frac{1+\lambda}{1-\lambda}\left[n-NP_N(n)\right] = \frac{1+\lambda}{1-\lambda}\left[n-N\frac{1-\lambda^n}{1-\lambda^N}\right] <–
E\left[\tau\right] = \frac{1+\lambda}{1-\lambda}\left[-n+NP_N(n)\right] = \frac{1+\lambda}{1-\lambda}\left[-n+N\frac{1-\lambda^n}{1-\lambda^N}\right]