Gambler's Ruin Problem

Consider the following questions:

  1. Suppose you have $20 and need $50 for a bus ride home. Your only chance to get more money is by gambling in a casino. There is only one possible bet you can make at the casino--you must bet $10, and then a fair coin is flipped. If ``heads'' results, you win $10 (in other words, you get your original $10 back plus an additional $10), and if it's ``tails'', you lose the $10 bet. The coin has exactly the same $ 50\%$ probability of coming up heads or tails. What is the chance that you will get the $50 you need? What if you had begun with $10? What if you had begun with $30?

  2. Same as above, except this time you start with $40 and need $100 for the bus ticket. But this time, you can bet either $10 or $20 on each flip. What's your best betting strategy?

  3. Real casinos don't give you a fair bet. Suppose the problem is the same as above, except that you have to make a $10 bet on ``red'' or ``black'' on a roulette wheel. A roulette wheel in the United States has 18 red numbers, 18 black numbers and 2 green numbers. Winning a red or black bet doubles your money if you win (and you lose it all if you lose), but obviously you now have a slightly smaller chance of winning. A red or black bet has a probability of $ 18/38 = 9/19$ of winning on each spin of the wheel. Answer all the questions above if your bets must be made on a roulette wheel.

All of these problems are known as the ``Gambler's Ruin Problem''--a gambler keeps betting until he goes broke, or until he reaches a certain goal, and there are no other possibilities. The problem has many elegant solutions which we will ignore. Let's just assume we're stupid and lazy, but we have a computer available to simulate the problem. Here is a nice matrix-based approach for stupid lazy people.

At any stage in the process, there are six possible states, depending on your ``fortune''. You have either $0 (and you've lost), or you have $10, $20, $30, $40 (and you're still playing), or you have $50 (and you've won). You know that when you begin playing, you are in a certain state (having $20 in the case of the very first problem). After you've played a while, lots of different things could have happened, so depending on how long you've been going, you have various probabilities of being in the various states. Call the state with $0 ``state 0'', and so on, up to ``state 5'' that represents having $50.

At any particular time, let's let $ p_0$ represent the probability of having $0, $ p_1$ the probability of having $10, and so on, up to $ p_5$ of having won with $50.

We can give an entire probabalistic description of your state as a column vector like this:

$\displaystyle \begin{pmatrix}p_0\\ p_1\\ p_2\\ p_3\\ p_4\\ p_5\end{pmatrix}. $

Now look at the individual situations. If you're in state 0, or in state 5, you will remain there for sure. If you're in any other state, there's a 50% chance of moving up a state and a 50% chance of moving down a state. Look at the following matrix multiplication:

$\displaystyle \begin{pmatrix}1&.5&0&0&0&0\\ 0&0&.5&0&0&0\\ 0&.5&0&.5&0&0\\ 0&0&... ..._0+.5p_1\\ .5p_2\\ .5p_1+.5p_3\\ .5p_2+.5p_4\\ .5p_3\\ .5p_4+p_5 \end{pmatrix}.$ (3)

Clearly, multiplication by the matrix above represents the change in probabilities of being in the various states, given an initial probabalistic distribution. The chance of being in state 0 after a coin flip is the chance you were there before, plus half of the chance that you were in state 1. Check that the others make sense as well.

So if the matrix on the left in equation (3) is called $ P$, each time you multiply the vector corresponding to your initial situation by $ P$, you'll find the probabilities of being in the various states. So after 1000 coin-flips, your state will be represented by $ P^{1000}v$, where $ v$ is the vector representing your original situation ( $ p_0 = p_1 = p_3 = p_4 = p_5 = 0$ and $ p_2 = 1$).

But multiplying $ P$ by itself 1000 times is a pain, even with a computer. Here's a nice trick: If you multiply $ P$ by itself, you get $ P^2$. But now, you can multiply $ P^2$ by itself to get $ P^4$. Then multiply $ P^4$ by itself to get $ P^8$, and so on. With just 10 iterations of this technique, we can work out $ P^{1024}$, which could even be done by hand, if you were desperate enough.

Here's what the computer says we get when we calculate $ P^{1024}$ to ten digits of accuracy:

$\displaystyle \begin{pmatrix} 1 & .8 & .6 & .4 & .2 & 0 \\ 0 & 1.549\times 10^... ...5} & 0 & 1.549\times 10^{-95} & 0 \\ 0 & .2 & .4 & .6 & .8 & 1 \end{pmatrix}. $

For all practical purposes, we have:

$\displaystyle P^{1024} = \begin{pmatrix} 1 & .8 & .6 & .4 & .2 & 0 \\ 0 & 0 & ... ...& 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & .2 & .4 & .6 & .8 & 1 \end{pmatrix}. $

Basically, if you start with $0, $10, ..., $50, you have probabilities of 0, .2, .4, .6, .8, and 1.0 of winning (reaching a goal of $50), and the complementary probabilities of losing. As we said above, this can be proven rigorously, but just multiplying the transition matrix by itself repeatedly strongly implies the result.

To solve the second problem, simply do the same calculation with either 6 states (a $ 6\times 6$ matrix) or 11 states (an $ 11\times 11$ matrix) and find a high power of the matrix. You'll find it doesn't make any difference which strategy you use.

On the final problem, you can use exactly the same technique, but this time the original matrix $ P$ will not have entries of $ .5$, but rather of $ 9/19$ and $ 10/19$. But after you know what $ P$ is, the process of finding a high power of $ P$ is exactly the same. In general, if you have a probability $ p$ of winning each bet and a probability of $ q = 1-p$ of losing, here's the transition matrix calculation:

$\displaystyle \begin{pmatrix} 1 & q & 0 & 0 & 0 & 0 \\ 0 & 0 & q & 0 & 0 & 0 \... ...trix}p_0+ qp_1\\ qp_2\\ pp_1+qp_3\\ pp_2+qp_4\\ pp_3\\ pp_4+p_5 \end{pmatrix}. $