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 denote the gambler’s fortune at time . Then is a martingale because

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

Thus,

and hence

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

Since ‘s are i.i.d., Wald’s equation can be used to find thestopping time. As , we use the second Wald’s equation

Observe that . Then,

#### Biased Game

Now suppose that the probability of winning . The tricky part in this case is to construct the martingale. Let and . Then is a martingale. In particular

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

So

which simplifies to

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

Note that

Thus,

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

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

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]