Gambler's ruin - 2

Continued from this note.

So far, we have examined the gambler's ruin problem on a small example. What can we say abut the more general case of starting out at some budget $k$ and deciding to cash out at some threshold $n$?

SPOILERS AHEAD. Please solve the problem before reading on.

There are the number of ways to tackle this, but the approach I'm going to take is to set up a system of linear equations. Let $r_{k,n}$ denote the probability we want to compute, namely the probability that, starting out at a budget of $k$ you will lose all your money before you ever hit $n$.

Since it is pessimistic to talk about ruin, let's set up the system in terms of variables representing the probabilities of winning, i.e. the probability of cashing out at $n$. In what follows, we will keep $n$ fixed, and so we will subscript the variables with only the budget.

For $0 \le i \le n$, let $w_{i}$ be the probability that you cash out, starting from an initial budget of $i$. We want to compute $w_{k}$. If you play the game once, then with probability 1/2 you increase your budget by 1 and with probability 1/2 you decrease it by one. And then you get to play again, as if you were starting with your new budget. Thus

• $w_0 =0$ -- If you have no money you can't play, and therefore can't win.
• $w_{i} = \frac{1}{2} (w_{i-1} + w_{i+1})$ for $1\le i\le n-1$
• $w_{n} = 1$ -- Because of your decision to take the money and quit when you reach $n$.

This gives a system of linear equations in $w_0 \dots w_n$. Combining the first two of these we easily see that $w_2 = 2w_1$ We will use this as a base case of an induction. Now suppose it is true that $w_{i} = i w_1$ for all $i<j \le n$. Then we'll show it is also true for $j$ as follows: We know that $w_{j-1} = \frac{w_{j-2}+w_{j}}{2} \,.$ Using the induction hypothesis to substitute for $w_{j-1}$ and $w_{j-2}$ we have $w_{j} = 2(j-1)w_1 - (j-2) w_1 = j w_1 \,.$ But now, using the fact that $w_n =1$, we have $w_1 = \frac{1}{n}$, and finally $w_k = \frac{k}{n}$ It follows that the probability of ruin is $\frac{n-k}{n}$.

Now what about the question of how long you play for?

Again, setting up a system of linear equations solves the problem. This time the equations we have are - $g_0 = g_n =0$ and - $g_{i} = 1+ \frac{ g_{i-1} + w_{g+1}}{2}$ for $1\le i\le n-1$ where $g_i$ is the expected number of games starting at a budget of $i$. It is not too hard to solve this and see that we get $g_k = k(n-k)$

To be continued...