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.