Stochastic processes - Gambler's ruin
You are entering a casino to win some money to pay your ex-wife's child support. Drunk, you stumble to the roulette table, look the croupier dead in the eye and say:
"You've changed your shirt, Mr. Bond. I do hope our little game isn't causing you to conspire?"
"It's perspire, you idiot, and this is not poker," he says, and asks whether you are here to place a bet or to quote movies.
You are $6 short of what you owe in child support, so you have no other option than to place a bet. But since you are not only drunk but also a cheap bastard, you set yourself a hard limit on how much you are willing to lose ($6).
Actually you have plenty of other options. Roulette was just the closest game to the bar.
The goal
We need to figure out what the probability is of turning $6 into $12 before you lose the $6.
Roulette rules
The American version of roulette has 38 pockets with different colors, 18 are red, 18 are black and only 2 are green.
Here is the probability distribution of a single spin with a $1 bet on red.
| Outcome | Probability | Net |
|---|---|---|
| Red | 0.4737 | +$1 |
| Black | 0.4737 | −$1 |
| Green | 0.0526 | −$1 |
Win 47.37% Lose 52.63%
Read this table as "If you place $1 on red there is a 47.37% chance of you winning $1".
Limitations
- You sit down with $6 (lol)
- If you reach $0 you walk away
- Your target is to reach $12, then you walk away
Symbols
| n | the spin counter (0, 1, 2, …) |
| Xₙ | your bankroll after n spins |
| T | your target, you quit if you reach it ($) |
| p | probability of winning a spin (18/38) |
| q | probability of losing a spin (20/38) |
These symbols might seem scary so I will try to make you feel comfortable with them. The core reason for using symbols is to be able to describe many things as one.
Let's look at some examples.
X₃ = $7 Your bankroll after spin number 3 is $7.
X₃ > X₂ Your bankroll after spin 3 is more than it was after spin 2, so you won spin 3.
p < q Your probability of winning is less than your probability of losing.
X₇ = T Your bankroll after spin 7 is equal to your target ($12).
The Markov property (side note)
Now let me ask you a question, given the following sequence of spins:
X₀ = $6, X₁ = $7, X₂ = $6, X₃ = $7
You started at $6 and you are back at $7 after the third spin.
What is the probability of going from where you are now ($7) to $6 or $8?
It is still the same:
$8 47.37% $6 52.63%
But what if we deleted the whole history of how we got to $7 and kept only the last value?
X₀ = $6, X₁ = $7, X₂ = $6, X₃ = $7
Would we still be able to determine the probability of going from $7 to $6 or $8?
Yes. You only need to know the current state of your bankroll (X) to know what happens next. How you got there doesn't matter.
And that, my friend, is called the Markov property:
"To guess what happens next, you only need the present situation"…
Transition probability
To describe going from your current bankroll to the next, we use:
P(i, j)
Reads: the probability of going from bankroll j.
P($7, $8) = 47.37%
Reads: the probability of going from $7 to $8 is 47.37%.
P($12, $12) = 100% P($0, $0) = 100%
These two are special cases. They describe the fact that you either reached your goal ($12) or lost all your money ($0). They are called "absorbing states", and it means that once you reach them you cannot get out of them.
Example:
If your bankroll reaches $0 on spin 9 (X₉ = $0), this is how the transition probabilities look for the upcoming spins:
| Spin | Probability |
|---|---|
| X₉ | P($0, $0) = 100% |
| X₁₀ | P($0, $0) = 100% |
| X₁₁ | P($0, $0) = 100% |
It's important to note that the game of roulette goes on with or without you participating, so we keep counting spins even after you have walked away. You are just stuck on the same number forever.
Transition matrix
When I first saw a transition matrix I got very confused, because it was a lot of rows and columns, so I am going to do my best explaining it.
A matrix is basically a table of rows and columns that you can read the same way you read a spreadsheet. We can use one to lay out every possible outcome of a single spin and the probability of that outcome.
We are going to start with a small one, where the rule is that you walk away when your bankroll hits $0 or $4 instead of $12.
In the above example the rows ($0 to $4) represent your current bankroll (Xₙ) and the column headers represent the bankroll you could move to. The cell where a row and a column meet is the probability of that move.
Example: If your current bankroll is $2 your only outcomes are either L (loss) or W (win), where loss is the transition from $2 to $1 and win is the transition from $2 to $3.
Now we replaced the symbols for win and loss with actual probabilities from a roulette game.
Example: If your current bankroll is $2 your probability of winning is 47% and your probability of losing is 53%. But also look at the top left and bottom right corner, that's our special case.
It says: if your current bankroll is $4 the probability of STAYING there is 100%, in other words P($4, $4) = 100%. Because remember, when we hit $4 in this example we leave (absorbing state).
And the same is true when the bankroll is $0 and we leave the table, in other words P($0, $0) = 100%.
Here is the transition matrix for our original game, where we start at $6 and leave when the bankroll is $12 (goal) or $0.
Predicting the future
The previous transition matrices showed us the probabilities of moving from one bankroll to another for a single spin. But it turns out we can also calculate the probabilities for where your bankroll will be after n spins.
Let's go back to the smaller example where our goal is to reach $4 instead of $12, and let's look at the table after 8 spins.
This table reads a bit differently than the previous ones. Every row still starts from a bankroll, but the columns now tell you where you are after 8 spins instead of after 1 spin.
The two absorbing columns, $0 and $4, are the interesting ones. Since you can never leave $0 or $4 once you land there, the number in those columns is the probability that you hit that amount at some point during the 8 spins and stayed there. The other columns are different: they only tell you where you are on spin 8 exactly.
Example: When you START with a $2 bankroll, the probability that you went broke at $0 at some point during those 8 spins is 52%.
There is also a 42% probability that you cashed out at $4 at some point during those 8 spins, and a 6% probability that the game is still running and you are sitting at $2 on spin 8.
The percentages in the table are rounded, so a row can add up to slightly more or less than 100%.
It's time to update our map over the different symbols. Let me introduce the symbol P, which represents the transition table. When we write it like this, P⁸, we are referencing the table after 8 spins.
| n | the spin counter (0, 1, 2, …) |
| Xₙ | your bankroll after n spins |
| X₀ | your starting bankroll ($6) |
| T | your target, you quit if you reach it ($) |
| p | probability of winning a spin (18/38) |
| q | probability of losing a spin (20/38) |
New symbols
| P(i, j) | the chance one spin takes you from j |
| P | the table of every P(i, j), the transition matrix |
| Pⁿ | the same table after n spins |
Can we reach $12?
| n | hit $12 | broke | still playing |
|---|---|---|---|
| 6 | 1.1% | 2.1% | 96.7% |
| 10 | 4.7% | 8.9% | 86.4% |
| 20 | 13.5% | 25.5% | 61.0% |
| 30 | 19.9% | 37.5% | 42.5% |
| 50 | 27.5% | 51.8% | 20.7% |
| 75 | 31.7% | 59.6% | 8.7% |
| 100 | 33.5% | 63.1% | 3.4% |
| 200 | 34.7% | 65.2% | 0.1% |
| 500 | 34.7% | 65.3% | 0.0% |
Read a row like this:
By spin 50, 27.5% have cashed out at $12, 51.8% are broke, and 20.7% are still playing.
Your first intuition might be "HEY, the more I play the higher the probability of winning!", WRONG!
The hit $12 column is not your odds getting better. It is a count of how many people have already finished. Watch the still playing column instead. It starts at 96.7% and drains to 0%, and everyone who leaves it lands in one of the other two columns.
That is the whole point. Your chance of turning $6 into $12 was 34.7% before you placed your first bet. More spins do not improve it, they just decide it faster.
The lesson here is that even though the casino only has a 5.26% edge on a single spin, that edge compounds over many spins. By spin 500 it has turned into 65.3% against 34.7%, which means the casino walks away a winner 88% more often than you do.
Your bankroll is the other half of the story. The longer you play, the bigger the swings get in both directions. After about 36 spins you are typically $6 away from where you started, in one direction or the other. That is your entire bankroll.
If it goes your way:
Spin: 36
| Player | Swing | Bankroll | Status |
|---|---|---|---|
| You | +$6 | $12 | Cashed out |
| Casino | −$6 | $∞ | Playing |
If it goes the casino's way:
Spin: 36
| Player | Swing | Bankroll | Status |
|---|---|---|---|
| You | −$6 | $0 | Broke |
| Casino | +$6 | $∞ | Playing |
A $6 swing ends your game either way. The casino does not even notice it. That is the difference, you have a floor at $0 and a ceiling at $12, and the casino has neither.
That is why, even if roulette were a fair 50/50 game with no green pockets, you would still go broke eventually if you sat there with no cash out target. Not because the game is unfair, but because you can run out of money and the casino cannot.