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 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}$

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.

About these ads

One thought on “A martingale solution to gambler’s ruin”

jihong lee on July 10, 2011 at 4:34 am said:

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

Reply ↓

Random Determinism

A martingale solution to gambler’s ruin

Fair Game

Biased Game

One thought on “A martingale solution to gambler’s ruin”

Leave a Reply Cancel reply

Follow “Random Determinism”

Fair Game

Biased Game

Rate this:

Share this:

Like this:

One thought on “A martingale solution to gambler’s ruin”

Leave a Reply Cancel reply

Follow “Random Determinism”