This post discusses the problem of the gambler’s ruin. We start with a simple illustration.
Intuitively, one might guess that player B is more likely to win all the coins since B begins the game with more coin. For example, player A in the example has only 1 coin to start. Thus there is a 50% chance that he/she will lose everything on the first toss. On the other hand, player B has a cushion since he/she can afford to lose some tosses at the beginning.
Simulated Plays of the Game
One way to get a sense of the winning probability of a player is to play the game repeatedly. Rather than playing with real money, why not simulate a series of coin tosses using random numbers generated in a computer? For example, the function =RAND() in Excel generates random numbers between 0 and 1. If the number is less than 0.5, we take it as a tail (T). Otherwise it is a head (H). As we simulate the coin tosses, we add or subtract to each player’s account accordingly. If the coin toss is a T, we subtract 1 from A and add 1 to B. If the coin toss is an H, we add 1 to A and subtract 1 from B. Here’s a simulation of the game.
In the first simulation, player A got lucky with 4 heads in 5 tosses. The following shows the next simulation.
Player A seems to be on a roll. Here’s the results of the next two simulated games.
Now player A loses both of these games. For good measure, we show one more simulation.
This one is a little more drawn out. Several tosses of tail in a row spells bad news for player A. When a coin is tossed long enough, there bounds to be some runs of tails. Since it is a fair coin, there bounds to be runs of head too, which benefit player A. Wouldn’t the runs of H cancel out the runs of T so that each player wins about half the time? To get an idea, we continue with 95 more simulations (to get a total of 100). Player A wins 23 of the simulated games and player B wins 77 of the games. So player A wins about 25% of the times. Note that A owns about 25% of the coins at the start of the game.
The 23 versus 77 in the 100 simulated games may be just due to luck for player B. We simulate 9 more runs of 100 games each (for a total of 10 runs with 100 games each). The following shows the results.
Ten Simulated Runs of 100 Games Each
The simulated runs fluctuate quite a bit. Player A wins any where from 19% to 34% of the times. The results are no where near even odds of winning for player A. In the 1,000 simulated games, player A wins 24.6% of the times, roughly identical to the player A’s share of the coins at the beginning. If the simulation is carried many more times (say 10,000 times or 100,000 times), the overall winning probability for player A would be very close to 25%.
Gambler’s Ruin Problem
Here’s a slightly more general description of the problem of gambler’s ruin.
Gambler’s Ruin Problem
Solution: Gambler’s Ruin Problem
In other words, the probability of winning for a player is the ratio of the number of coins the player starts with to the total numbers of coins. Turning it around, the probability of a player losing all his/her coins is the ratio of the number of coins of the other player to the total number of coins. Thus the player with the fewer number of coins at the beginning has a greater chance of losing everything. Think a casino. Say, it has 10,000,000 coins. You, as a gambler, have 100 coins. Then you would have a 99.999% chance of losing all your coins.
The 99.999% chance of losing everything is based on the assumption that all bets are at even odds. This is certainly not the case in a casino. The casino enjoys a house edge. So the losing probabilities would be worse for a gambler playing in a casino.
Deriving the Probabilities
We derive the winning probability for a more general case. The coin that is tossed does not have to be a fair coin. Let be the probability that the coin toss results in a head. Let . Suppose that there are coins initially between player A and player B.
Let be the probability that player A will own all the coins when player A starts the game with coins and player B starts with coins. On the other hand, let be the probability that player B will own all the coins when player A starts the game with coins and player B starts with coins.
The goal here is to derive expressions for both and for and to show that . The last point, though seems like common sense, is not entirely trivial. It basically says that the game will end in finite number of moves (it cannot go on indefinitely).
Another point to keep in mind is that we can assume and as well as and . In the following derivation, is the event that the first toss is a head and is the event that the first toss is a tail.
Let be the event that player A owning all the coins when player A starts the game with coins and player B starts with coins, i.e. . First condition on the outcome of the first toss of the coin.
Consider the conditional probabilities and . Note that . If the first toss is a head, then player A has coins and player B would have coins. At that point, the probability of player A owning all the coins would be the same as the probability of winning as if the game begins with player A having coins. Similarly, . Plug these into (1), we have:
Further derivation can be made on equation (2).
Plugging in the values for produces the following equations.
Adding the first equations produces the following equations.
There are two cases to consider. Either or . The first case means and the second case means . The following is an expression for for the two cases.
The above two-case expression for is applicable for . Plugging into with gives the following expression for :
Plugging from (5) into (4) gives the following:
The expression for in (6) is applicable for . For the case of , the probability of player A owning all the coin is the ratio of the initial amount of coins of player A to the total number of coins, identical to what is stated in the previous section. Recall that is the probability that player B will end up owning all the coins when initially player A has coins and player B has coins. By symmetry, the following gives the expression for .
For the case , which is equivalent to , it is clear that . For the case , the following shows that .
The fact that shows that the gambling game discussed here has to end after certain number of plays and that it will not continue indefinitely.
The formulas derived here are quite profound, not to mention impactful and informative for anyone who gambles. More calculations and discussion can be found here in a companion blog on statistics.
2017 – Dan Ma