Gambler's ruin
The term gambler's ruin is a statistical concept expressed in a variety of forms:
- The original meaning is that a persistent gambler who raises his bet to a fixed fraction of bankroll when he wins, but does not reduce it when he loses, will eventually and inevitably go broke, even if he has a positive expected value on each bet.
- Another common meaning is that a persistent gambler with finite wealth, playing a fair game will eventually and inevitably go broke against an opponent with infinite wealth. Such a situation can be modeled by a random walk on the real number line. In that context it is provable that the agent will return to his point of origin or go broke and is ruined an infinite number of times if the random walk continues forever.
- The result above is a corollary of a general theorem by Christiaan Huygens which is also known as gambler's ruin. That theorem shows how to compute the probability of each player winning a series of bets that continues until one's entire initial stake is lost, given the initial stakes of the two players and the constant probability of winning. This is the oldest mathematical idea that goes by the name gambler's ruin, but not the first idea to which the name was applied.
- The most common use of the term today is that a gambler playing a negative expected value game will eventually go broke, regardless of betting system. This is another corollary to Huygens's result.
- The concept may be stated as an ironic paradox: Persistently taking beneficial chances is never beneficial at the end. This paradoxical form of gambler's ruin should not be confused with the gambler's fallacy, a different concept.
History
The earliest known mention of the gambler's ruin problem is a letter from Blaise Pascal to Pierre Fermat in 1656. Pascal's version was summarized in a 1656 letter from Pierre de Carcavi to Huygens:Let two men play with three dice, the first player scoring a point whenever 11 is thrown, and the second whenever 14 is thrown. But instead of the points accumulating in the ordinary way, let a point be added to a player's score only if his opponent's score is nil, but otherwise let it be subtracted from his opponent's score. It is as if opposing points form pairs, and annihilate each other, so that the trailing player always has zero points. The winner is the first to reach twelve points; what are the relative chances of each player winning?
Huygens reformulated the problem and published it in De ratiociniis in ludo aleae :
Problem Each player starts with 12 points, and a successful roll of the three dice for a player adds one to that player's score and subtracts one from the other player's score; the loser of the game is the first to reach zero points. What is the probability of victory for each player?This is the classic gambler's ruin formulation: two players begin with fixed stakes, transferring points until one or the other is "ruined" by getting to zero points. However, the term "gambler's ruin" was not applied until many years later.
Reasons for the four results
Let "bankroll" be the amount of money a gambler has at his disposal at any moment, and let N be any positive integer. Suppose that he raises his stake to when he wins, but does not reduce his stake when he loses. This general pattern is not uncommon among real gamblers, and casinos encourage it by "chipping up" winners. Under this betting scheme, it will take at most N losing bets in a row to bankrupt him. If his probability of winning each bet is less than 1, he will eventually lose N bets in a row, however big N is. It is not necessary that he follow the precise rule, just that he increase his bet fast enough as he wins. This is true even if the expected value of each bet is positive.The gambler playing a fair game will eventually either go broke or double his wealth. Let's define that the game ends upon either event. These events are equally likely, or the game would not be fair. So he has a 0.5 chance of going broke before doubling his money. Given he doubles his money, a new game begins and he again has a 0.5 chance of doubling his money before going broke. After the second game there is a 1/2 x 1/2 chance that he has not gone broke in the first and second games. Continuing this way, his chance of not going broke after n successive games is 1/2 x 1/2 x 1/2 x... 1/2^n which approaches 0. His chance of going broke after n successive games is 0.5 + 0.25 + 0.125 +... 1 - 1/2^n which approaches 1.
Huygens's result is illustrated in the next section.
The eventual fate of a player at a negative expected value game cannot be better than the player at a fair game, so he will go broke as well.
Example of Huygens's result
Fair coin flipping
Consider a coin-flipping game with two players where each player has a 50% chance of winning with each flip of the coin. After each flip of the coin the loser transfers one penny to the winner. The game ends when one player has all the pennies.If there are no other limitations on the number of flips, the probability that the game will eventually end this way is 1.
If player one has n1 pennies and player two n2 pennies, the probabilities P1 and P2 that players one and two, respectively, will end penniless are:
Two examples of this are if one player has more pennies than the other; and if both players have the same number of pennies.
In the first case say player one has 8 pennies and player two were to have 5 pennies then the probability of each losing is:
It follows that even with equal odds of winning the player that starts with fewer pennies is more likely to fail.
In the second case where both players have the same number of pennies the likelihood of each losing is:
Unfair coin flipping
In the event of an unfair coin, where player one wins each toss with probability p, and player two wins with probability q = 1 − p, then the probability of each ending penniless is:This can be shown as follows: Consider the probability of player 1 experiencing gamblers ruin having started with amount of money,. Then, using the Law of Total Probability, we have
where W denotes the event that player 1 wins the first bet. Then clearly and. Also is the probability that player 1 experiences gambler's ruin having started with amount of money: ; and is the probability that player 1 experiences gambler's ruin having started with amount of money:.
Denoting, we get the linear homogeneous recurrence relation
which we can solve using the fact that , and For a more detailed description of the method see e.g. Feller, An introduction to probability theory and its applications, 3rd ed.
''N''-player ruin problem
The above described problem is a special case of the so-called N-Player ruin problem.Here players with initial capital dollars, respectively,
play a sequence of independent games and win and lose certain amounts of dollars from/to each other according to fixed rules.
The sequence of games ends as soon as at least one player is ruined. Standard Markov chain methods can be applied to
solve in principle this more general problem, but the computations quickly become prohibitive as soon as the number of players
or their initial capital increase. For and large initial capitals
the solution can be well approximated by using two-dimensional Brownian motion.
In practice the true problem is to find the solution for the typical cases of and limited initial capital.
Swan proposed an algorithm based on Matrix-analytic methods which significantly
reduces the order of the computational task in such cases.