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]


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 thestopping 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]


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}


\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.