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.


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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s