Recently, I needed to use a result that was, at the heart of it, a glorified gambler’s ruin problem. I have not looked at gambler’s ruin for a while, so thought that it will be fun to rederive the results. Gambler’s ruin refers to various scenarios, the most common of which is the following.

A gambler enters a casino with $n in cash and starts playing a game where he wins with probability p and looses with probability q = 1-p The gampler plays the game repeatedly, betting $1 in each round. He leaves the gave it his total fortune reaches $N or he runs out of money (he is ruined), whichever happens first. What is the probability that the gambler is ruined.

A gambler’s ruin can be modeled as a one-dimensional random walk in which we are interested in the hitting probability of the absorbing states. Calculating these probabilities is fairly straightforward. Let P_N(n) denote the probability that the gambler’s fortune reaches $N before he is ruined on the condition that his current fortune is n. Then,

P_N(n) = p P_N(n+1) + q P_N(n-1)

which can be rewritten as

\displaystyle [P_N(n+1) - P_N(n)] = \left(\frac q p \right)[ P_N(n) - P_N(n-1)]

Since P_N(0) = 0, we have that

\displaystyle P_N(2) - P_N(1) = \left(\frac qp \right) P_N(1)

and similarly

\displaystyle P_N(3) - P_N(2) = \left(\frac qp \right) [P_N(2) - P_N(1)] = \left( \frac qp \right)^2 P_N(1)

Continuing this way, we get that

\displaystyle P_N(n) - P_N(n-1) = \left( \frac qp \right)^{n-1} P_N(1) .

and therefore, by adding the first n such terms, we get

\displaystyle P_N(n) = \sum_{k=0}^{n-1} \left( \frac qp \right)^k P_N(1).

Moreover, we know that

\displaystyle P_N(N) = \sum_{k=0}^{N-1} \left( \frac qp \right)^k P_N(1) = 1.

Thus,

\displaystyle P_N(1) = \frac 1{\sum_{k=0}^{N-1} \left( \frac qp \right)^k} = \begin{cases} \frac { 1 - (q/p)}{\strut 1 - (q/p)^N}, & p \neq q \\ \frac 1N, & p = q \end{cases}.

Combining with the previous expression for P_N(n) we get,

\displaystyle P_N(n) = \begin{cases} \frac{ 1 - (q/p)^n} {\strut 1 - (q/p)^N}, & p \neq 1/2 \\ \frac{n}{N}, & p = 1/2 \end{cases}.

For ease of representation let \lambda = q/p. Then, the probability of winning are

\displaystyle P_N(n) = \begin{cases} \frac{ 1 - \lambda^n} {\strut 1 - \lambda^N}, & \lambda \neq 1 \\ \frac{n}{N}, &\lambda = 1 \end{cases}.

This was simple, but I am interested in finding the expected time when the game stops.

Expected number of steps until stopping

Let C_N(n) denote the number of plays until the game stops on the condition that the player’s current fortune is $n. As before, we can write

\displaystyle C_N(n) = p C_N(n+1) + q C_N(n-1) + 1.

Rewriting this and observing 1/p = (1 + \lambda), we get

\displaystyle C_N(n+1) - C_N(n) = \lambda [ C_N(n) - C_N(n-1)] + (1 + \lambda).

Rearranging terms, we have

\displaystyle C_N(n+1) - C_N(n) - \frac { 1 + \lambda} {1 - \lambda} = \lambda \left[ C_N(n) - C_N(n-1) - \frac {1+ \lambda}{1-\lambda} \right].

Since $C_N(0) = 0$, we have that

\displaystyle C_N(2) = 2 \alpha + \lambda[ C_N(1) - \alpha] .

where \alpha = (1+\lambda)/(1-\lambda). And similarly,

\displaystyle C_N(3) - C_N(2) - \alpha = \lambda[ C_N(2) - C_N(1) - \alpha] = \lambda^2 [ C_N(1) - \alpha] .

Continuing this way, we have that

\displaystyle C_N(n) - C_N(n-1) - \alpha = \lambda^{n-1}[ C_N(1) - \alpha] .

Adding the first n such terms, we get

\displaystyle C_N(n) = n \alpha + \sum_{k=0}^{n-1} \lambda^k [ C_N(1) - \alpha] .

Moreover, we know that C_N(N) = 0. Thus,

\displaystyle [C_N(1) - \alpha ] = -\frac{N \alpha}{\sum_{k=0}^{N-1} \lambda^k }= \frac {N (1+\lambda}{1 - \lambda^N}.

Substituting this back in the expression for C_N(n), we get

\displaystyle C_N(n) = \frac{ (1+\lambda)}{(1 - \lambda)} \left[ n - N \frac{ (1 - \lambda^n)}{(1 - \lambda^N)} \right].

When \lambda = 1, we obtain a simplified expression

\displaystyle C_N(n) = \left( \frac N2 \right)^2 - \left( n - \frac N2 \right)^2 = n(N-n).

OK. Itch scratched. That feels better.

Advertisement