Gambler’s Ruin Problem: A Probability Antiquity | by Naman Agrawal | Nov, 2022
Understanding one of the most famous problems in probability theory
Gambler’s ruin is one of the most essential concepts in Probability theory. Its first mention dates back to the 17th century in a letter exchange between Blaise Pascal and Pierre Fermat. The problem involves determining the probability that a gambler wins under the following conditions:
- They both start off with a fixed amount of money.
- The probability of either one of them winning is constant throughout the game.
- The game continues till either one of them runs out of money.
An example would be to consider two gamblers Raj and Mir. It is given that they start with ₹100 and ₹60 respectively. The gamblers bet on the outcomes of successive coin tosses. If the coin lands head, Raj wins and Mir has to give ₹1 to Raj. Else, Mir wins and Raj has to give ₹1 to Mir. The game continues till one of the players ends up losing all the money. It is also given that the coin is biased, that the probability it lands heads is 1/3. We would now like to determine the probability that Raj wins the game. Before we start solving this problem, a couple of things to take note of:
- We don’t know how many turns it will take for the game to get over, It is possible that Mir ends up losing every game, and the number of turns would be 60 in such a case. It is also possible that the game never terminates, in the case that each of them wins alternatively. Both of these cases are probable (though very low probability), and so are the infinitely possible other cases between them.
- While solving problems in Statistics (and also frequently in Computer Science), it’s often important to identify the problem invariant i.e., something about the problem that’s always going to be constant, something that does not change or depend on outcomes of the sub-problems. For us, the invariant is the total amount of money that the gamblers have. Regardless, of whatever state the game is, the sum of money that Raj and Mir have is constant: ₹100 + ₹60 = ₹160. The only thing that’s changing is the amount of money that either of the gamblers has. How’s this useful to us? Well, this means that we only need to keep track of the money that one of the gamblers has at any given point in time. The other gambler’s money can be obtained by simply subtracting that amount from the total money that both gamblers have (invariant of the game). For instance, if Raj has ₹85 at some point in the game, we can say that Mir has ₹160— ₹85 = ₹75 at that instance. (Note that there are some variants of the problem where this may not hold true, we’ll be looking at one of those variants towards the end of this article).
- These problems are frequently modeled using Markov Chain models. But, in this article, we’ll be using the approach of conditional probability with some modeling techniques to simplify the approach. The key idea is to extend the game into the past and the future to account for different possibilities. We’ll be seeing how to do this later.
Let’s start by defining some events:
- Let R₁₀₀ denote the event that Raj wins the game given that he starts with ₹100. Note that the invariance means that we don’t have to keep track of the amount Mir has at the start of the game.
- Let H denote the event that the coin lands heads on the first flip.
- Let T denote the event that the coin lands tails on the first flip.
With these definitions, we can define P(R₁₀₀), the probability that Raj wins the game given that he starts with ₹100 by conditioning it on the outcome of the first flip:
Now, we observe that if Raj wins in the first game, then Raj ends up with ₹101. This can be interpreted as exactly the situation that Raj starts the game with ₹101. Likewise, if Raj loses in the first game, then Raj ends up with ₹99. This can be interpreted as exactly the situation that Raj starts the game with ₹99. Thus, we have:
Thus, we have managed to obtain, something that looks like a recurrence relationship. We’ve defined the probability of Raj winning given that he starts with ₹100 recursively in terms of the probability of him winning given that he starts with ₹101 and the probability of him winning given that he starts with ₹99. What remains is to solve the recurrence relation. To solve this recurrence problem, we need to extend the problem backward and/or forward in time until we reach a base condition i.e., some i such that P(Rᵢ) is known to us. How do we do so? Well, there are two base conditions that can help us solve the recursive problem:
1. If it was given to us that Raj started with ₹0, what can we say about the probability that Raj wins? Yes, it should be 0! Why? Because if Raj had no money to start with, he has already lost the game.
2. If it was given to us that Raj started with ₹160, what can we say about the probability that Raj wins? Yes, it should be 1! Why? Because if Raj had all the money to start with, he has already won the game.
Thus, we have the following pieces of information:
Before solving this recursive problem, we write down the recurrence relationship in a slightly different way to simplify our solution:
Now that we’ve obtained a recurrence relationship and the base condition, we can solve the recurrence formula by tracing the game backward and forward in time. Sweet! This gives us:
We’ve taken the value of i to go from 1 to 159 because our recurrence relationships will permit a maximum value of i + 1 = 159 + 1 =160 (the maximum amount Raj can have) and a minimum value of i — 1 = 1–1 = 0 (the minimum amount Raj can have). We substitute the base case solutions at 0 and 160, to give us the following results:
If we add the first 99 equations (1 ≤ i ≤ 99), we get:
Note how the form of writing the recurrence relationship allows us to cancel all the terms leaving us with just two of them. Also, note that we’ve used the formula of geometric series to calculate the sum of powers of two. Now, if we know P(R₁), we can calculate P(R₁₀₀) and that will solve our problem! To find P(R₁), we add all the 159 equations shown previously and use the second base condition that P(R₁₆₀) = 1:
Substituting this result into equation (i), we get:
Some of us might find the result surprising considering that Raj started with a much higher amount. But, once you realize that the chances of Raj winning are about half of that of Mir winning at every game, you’ll soon understand why the probability values start to decay exponentially, giving us an almost 0 probability of Raj winning the game.
In fact, you can generalize the above formula given that Raj starts with some amount ₹A, and Mir starts with some amount ₹B. If the probability of heads was given to be α, then your recurrence relationship and base cases would be given by:
Solving the above recurrence formula just as before will give us the following solution to the generalized Gamblers Ruin problem:
Note that the above equations holds only as long as α ≠ 0.5. If α = 0.5, the problem becomes quite trivial as the gambler with a higher amount of money is more likely to win since their winning probabilities for each game are the same. In such a situation, the solution would be trivially:
After solving this version of the Gambler’s ruin problem, let’s look at another version of the problem:
Consider two gamblers Raj and Mir. It is given that they start with ₹100 and ₹60 respectively. The gamblers bet on the outcomes of successive coin tosses. If the coin lands head, Raj wins and gets ₹1. Else, Mir wins and gets ₹1. The game continues till one of the players gets ₹150. It is also given that the coin is biased, that the probability it lands heads is 1/3. We would now like to determine the probability that Raj wins the game.
How’s this problem different from the previous problem?
- Winning conditions: The winner is now declared as the one who gets ₹150 first.
- In-variance: We no longer have the invariance property of the total amount in the game. Since transactions no longer involve a transfer of amount from Raj to Mir, there could be any indeterminate total amount of money at any point in the game. This means that we’ve to keep track of both the amount that Raj has and the amount that Mir has at any point in the game.
There are two ways to solve this variant of the Gambler’s Ruin. The first, suggested by Pascal involves following the same modeling strategy we used earlier: Conditioning the probability of Raj winning on the outcome of the first toss to obtain a recurrence relationship, identifying base cases, and solving the recurrence formulation to get the solution. Also, note that finding the probability that Raj wins is the same as determining the probability that Raj wins 50 games before Mir wins 90 games. So, we model the probabilities as follows:
We let R₍₅₀,₉₀₎ denote the event that Raj wins 50 games before Mir wins 90 games. Notice how we track both: the number of gains won by Raj and those won by Mir (due to the loss of the in-variance property we earlier had). Thus,
Now, we observe that if Raj wins in the first game, then Raj needs to win another 49 games. Likewise, if Mir wins in the first game, then Mir needs to win another 89 games. Thus,
Just as before, we may determine the base cases for our recursive problem:
- If it was given to us that Mir started with ₹150, (note that this corresponds to R₍₁₅₀,₀₎ what can we say about the probability that Raj wins? Yes, it should be 0! Why? Because if Mir has ₹150 to start with, Mir has already won the game.
- If it was given to us that Raj started with ₹150, (note that this corresponds to R₍₀,₁₅₀₎ what can we say about the probability that Raj wins? Yes, it should be 1! Why? Because if Raj has ₹150 to start with, Raj has already won the game.
Thus, we have the following pieces of information:
Just as before, we may solve the above recursion problem to obtain the desired probability. However, solving the above problem is much more complex now, given that we’re dealing with two variables to keep track of the number of games each of the players have to win to win the overall gamble. We may write a small computer program to solve the above problem. I’ve written the following recursive solution in Python to help us find the solutions (I’ve also added some memoization to speed things up):
def memoize(f):
table = {}
def helper(*args):
if args not in table:
table[args] = f(*args)
return table[args]
return helper@memoize
def gambler_ruin(r, m, p):
if r == 0:
return 1
if m == 0:
return 0
else:
return p*gambler_ruin(r-1, m, p) + (1-p)*gambler_ruin(r, m-1, p)
print(gambler_ruin(50, 90, 1/3))
Running the above program gives us the solution 0.282 to our problem i.e., the probability that Raj wins is 0.282, much higher than that in the previous example. This is because every time Mir won meant Raj lost ₹1 in the previous problem. But, for this problem even if Mir wins one game, Raj will still be required to win the same number of games to win the overall gamble.
Finally, let’s look at another way to solve this problem, which was earlier suggested by Fermat in his letter to Pascal. This involved modeling the problem as a binomial distribution. Recall that the binomial distribution gives us the probability of k successes in n trials, each success having a probability of p:
How do we model the problem using a binomial distribution? We are asked to find the probability that Raj wins 50 games before Mir wins 90 games. Thus, if 90 + 50 -1 = 139 games are performed, we are guaranteed to have a winner. Note that this is different from the previous problem as previously there was no limit on the number of tosses. A continuous alteration between Raj and Mir winning meant a possibility of infinite runs. However, for this problem, since we are guaranteed a winner in 139 games, we can use the binomial distribution to determine the probability of Raj winning.
Suppose, we extend the game to continue up to 139 tosses. If more than or equal to 50 of these 139 tosses are heads, Raj wins. Else, Mir wins. Let X be a random variable for the number of heads in 139 tosses, with each head having a probability of 1/3. Thus:
Thus, the winning probability of Raj is given by:
The above sum can be evaluated using any calculator (or writing another computer program). It should not come as a surprise both these methods give the same results.
Thus, we’ve discussed two versions of the Gamblers Ruin Problem, understood the implications of the problem conditions, and looked at some modeling strategies to solve those problems. The first step to approaching these problems involves identifying an apt model, one that is computationally feasible and makes use of any associated invariance properties. This is followed by building up the model, such as by conditioning the desired probability on the outcome of a specific sub-event. Once the model has been obtained, we proceed to use the model to obtain the optimal solutions. This can be done recursively (after identifying suitable base cases) or by exploiting the properties of some well-known probability distributions. Finally, we try to analyze the results of the model, trying to balance any conflict between intuition and experimental results.
Thanks for reading! Hope you enjoyed this article!
Understanding one of the most famous problems in probability theory
Gambler’s ruin is one of the most essential concepts in Probability theory. Its first mention dates back to the 17th century in a letter exchange between Blaise Pascal and Pierre Fermat. The problem involves determining the probability that a gambler wins under the following conditions:
- They both start off with a fixed amount of money.
- The probability of either one of them winning is constant throughout the game.
- The game continues till either one of them runs out of money.
An example would be to consider two gamblers Raj and Mir. It is given that they start with ₹100 and ₹60 respectively. The gamblers bet on the outcomes of successive coin tosses. If the coin lands head, Raj wins and Mir has to give ₹1 to Raj. Else, Mir wins and Raj has to give ₹1 to Mir. The game continues till one of the players ends up losing all the money. It is also given that the coin is biased, that the probability it lands heads is 1/3. We would now like to determine the probability that Raj wins the game. Before we start solving this problem, a couple of things to take note of:
- We don’t know how many turns it will take for the game to get over, It is possible that Mir ends up losing every game, and the number of turns would be 60 in such a case. It is also possible that the game never terminates, in the case that each of them wins alternatively. Both of these cases are probable (though very low probability), and so are the infinitely possible other cases between them.
- While solving problems in Statistics (and also frequently in Computer Science), it’s often important to identify the problem invariant i.e., something about the problem that’s always going to be constant, something that does not change or depend on outcomes of the sub-problems. For us, the invariant is the total amount of money that the gamblers have. Regardless, of whatever state the game is, the sum of money that Raj and Mir have is constant: ₹100 + ₹60 = ₹160. The only thing that’s changing is the amount of money that either of the gamblers has. How’s this useful to us? Well, this means that we only need to keep track of the money that one of the gamblers has at any given point in time. The other gambler’s money can be obtained by simply subtracting that amount from the total money that both gamblers have (invariant of the game). For instance, if Raj has ₹85 at some point in the game, we can say that Mir has ₹160— ₹85 = ₹75 at that instance. (Note that there are some variants of the problem where this may not hold true, we’ll be looking at one of those variants towards the end of this article).
- These problems are frequently modeled using Markov Chain models. But, in this article, we’ll be using the approach of conditional probability with some modeling techniques to simplify the approach. The key idea is to extend the game into the past and the future to account for different possibilities. We’ll be seeing how to do this later.
Let’s start by defining some events:
- Let R₁₀₀ denote the event that Raj wins the game given that he starts with ₹100. Note that the invariance means that we don’t have to keep track of the amount Mir has at the start of the game.
- Let H denote the event that the coin lands heads on the first flip.
- Let T denote the event that the coin lands tails on the first flip.
With these definitions, we can define P(R₁₀₀), the probability that Raj wins the game given that he starts with ₹100 by conditioning it on the outcome of the first flip:
Now, we observe that if Raj wins in the first game, then Raj ends up with ₹101. This can be interpreted as exactly the situation that Raj starts the game with ₹101. Likewise, if Raj loses in the first game, then Raj ends up with ₹99. This can be interpreted as exactly the situation that Raj starts the game with ₹99. Thus, we have:
Thus, we have managed to obtain, something that looks like a recurrence relationship. We’ve defined the probability of Raj winning given that he starts with ₹100 recursively in terms of the probability of him winning given that he starts with ₹101 and the probability of him winning given that he starts with ₹99. What remains is to solve the recurrence relation. To solve this recurrence problem, we need to extend the problem backward and/or forward in time until we reach a base condition i.e., some i such that P(Rᵢ) is known to us. How do we do so? Well, there are two base conditions that can help us solve the recursive problem:
1. If it was given to us that Raj started with ₹0, what can we say about the probability that Raj wins? Yes, it should be 0! Why? Because if Raj had no money to start with, he has already lost the game.
2. If it was given to us that Raj started with ₹160, what can we say about the probability that Raj wins? Yes, it should be 1! Why? Because if Raj had all the money to start with, he has already won the game.
Thus, we have the following pieces of information:
Before solving this recursive problem, we write down the recurrence relationship in a slightly different way to simplify our solution:
Now that we’ve obtained a recurrence relationship and the base condition, we can solve the recurrence formula by tracing the game backward and forward in time. Sweet! This gives us:
We’ve taken the value of i to go from 1 to 159 because our recurrence relationships will permit a maximum value of i + 1 = 159 + 1 =160 (the maximum amount Raj can have) and a minimum value of i — 1 = 1–1 = 0 (the minimum amount Raj can have). We substitute the base case solutions at 0 and 160, to give us the following results:
If we add the first 99 equations (1 ≤ i ≤ 99), we get:
Note how the form of writing the recurrence relationship allows us to cancel all the terms leaving us with just two of them. Also, note that we’ve used the formula of geometric series to calculate the sum of powers of two. Now, if we know P(R₁), we can calculate P(R₁₀₀) and that will solve our problem! To find P(R₁), we add all the 159 equations shown previously and use the second base condition that P(R₁₆₀) = 1:
Substituting this result into equation (i), we get:
Some of us might find the result surprising considering that Raj started with a much higher amount. But, once you realize that the chances of Raj winning are about half of that of Mir winning at every game, you’ll soon understand why the probability values start to decay exponentially, giving us an almost 0 probability of Raj winning the game.
In fact, you can generalize the above formula given that Raj starts with some amount ₹A, and Mir starts with some amount ₹B. If the probability of heads was given to be α, then your recurrence relationship and base cases would be given by:
Solving the above recurrence formula just as before will give us the following solution to the generalized Gamblers Ruin problem:
Note that the above equations holds only as long as α ≠ 0.5. If α = 0.5, the problem becomes quite trivial as the gambler with a higher amount of money is more likely to win since their winning probabilities for each game are the same. In such a situation, the solution would be trivially:
After solving this version of the Gambler’s ruin problem, let’s look at another version of the problem:
Consider two gamblers Raj and Mir. It is given that they start with ₹100 and ₹60 respectively. The gamblers bet on the outcomes of successive coin tosses. If the coin lands head, Raj wins and gets ₹1. Else, Mir wins and gets ₹1. The game continues till one of the players gets ₹150. It is also given that the coin is biased, that the probability it lands heads is 1/3. We would now like to determine the probability that Raj wins the game.
How’s this problem different from the previous problem?
- Winning conditions: The winner is now declared as the one who gets ₹150 first.
- In-variance: We no longer have the invariance property of the total amount in the game. Since transactions no longer involve a transfer of amount from Raj to Mir, there could be any indeterminate total amount of money at any point in the game. This means that we’ve to keep track of both the amount that Raj has and the amount that Mir has at any point in the game.
There are two ways to solve this variant of the Gambler’s Ruin. The first, suggested by Pascal involves following the same modeling strategy we used earlier: Conditioning the probability of Raj winning on the outcome of the first toss to obtain a recurrence relationship, identifying base cases, and solving the recurrence formulation to get the solution. Also, note that finding the probability that Raj wins is the same as determining the probability that Raj wins 50 games before Mir wins 90 games. So, we model the probabilities as follows:
We let R₍₅₀,₉₀₎ denote the event that Raj wins 50 games before Mir wins 90 games. Notice how we track both: the number of gains won by Raj and those won by Mir (due to the loss of the in-variance property we earlier had). Thus,
Now, we observe that if Raj wins in the first game, then Raj needs to win another 49 games. Likewise, if Mir wins in the first game, then Mir needs to win another 89 games. Thus,
Just as before, we may determine the base cases for our recursive problem:
- If it was given to us that Mir started with ₹150, (note that this corresponds to R₍₁₅₀,₀₎ what can we say about the probability that Raj wins? Yes, it should be 0! Why? Because if Mir has ₹150 to start with, Mir has already won the game.
- If it was given to us that Raj started with ₹150, (note that this corresponds to R₍₀,₁₅₀₎ what can we say about the probability that Raj wins? Yes, it should be 1! Why? Because if Raj has ₹150 to start with, Raj has already won the game.
Thus, we have the following pieces of information:
Just as before, we may solve the above recursion problem to obtain the desired probability. However, solving the above problem is much more complex now, given that we’re dealing with two variables to keep track of the number of games each of the players have to win to win the overall gamble. We may write a small computer program to solve the above problem. I’ve written the following recursive solution in Python to help us find the solutions (I’ve also added some memoization to speed things up):
def memoize(f):
table = {}
def helper(*args):
if args not in table:
table[args] = f(*args)
return table[args]
return helper@memoize
def gambler_ruin(r, m, p):
if r == 0:
return 1
if m == 0:
return 0
else:
return p*gambler_ruin(r-1, m, p) + (1-p)*gambler_ruin(r, m-1, p)
print(gambler_ruin(50, 90, 1/3))
Running the above program gives us the solution 0.282 to our problem i.e., the probability that Raj wins is 0.282, much higher than that in the previous example. This is because every time Mir won meant Raj lost ₹1 in the previous problem. But, for this problem even if Mir wins one game, Raj will still be required to win the same number of games to win the overall gamble.
Finally, let’s look at another way to solve this problem, which was earlier suggested by Fermat in his letter to Pascal. This involved modeling the problem as a binomial distribution. Recall that the binomial distribution gives us the probability of k successes in n trials, each success having a probability of p:
How do we model the problem using a binomial distribution? We are asked to find the probability that Raj wins 50 games before Mir wins 90 games. Thus, if 90 + 50 -1 = 139 games are performed, we are guaranteed to have a winner. Note that this is different from the previous problem as previously there was no limit on the number of tosses. A continuous alteration between Raj and Mir winning meant a possibility of infinite runs. However, for this problem, since we are guaranteed a winner in 139 games, we can use the binomial distribution to determine the probability of Raj winning.
Suppose, we extend the game to continue up to 139 tosses. If more than or equal to 50 of these 139 tosses are heads, Raj wins. Else, Mir wins. Let X be a random variable for the number of heads in 139 tosses, with each head having a probability of 1/3. Thus:
Thus, the winning probability of Raj is given by:
The above sum can be evaluated using any calculator (or writing another computer program). It should not come as a surprise both these methods give the same results.
Thus, we’ve discussed two versions of the Gamblers Ruin Problem, understood the implications of the problem conditions, and looked at some modeling strategies to solve those problems. The first step to approaching these problems involves identifying an apt model, one that is computationally feasible and makes use of any associated invariance properties. This is followed by building up the model, such as by conditioning the desired probability on the outcome of a specific sub-event. Once the model has been obtained, we proceed to use the model to obtain the optimal solutions. This can be done recursively (after identifying suitable base cases) or by exploiting the properties of some well-known probability distributions. Finally, we try to analyze the results of the model, trying to balance any conflict between intuition and experimental results.
Thanks for reading! Hope you enjoyed this article!
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.