Gambler's ruin

The term gambler's ruin is used for a number of related statistical ideas:

* The original meaning is that a gambler who raises his bet to a fixed fraction of bankroll when he wins, but does not reduce it when he loses, will eventually go broke, even if he has a positive expected value on each bet.

* Another common meaning is that a gambler with finite wealth, playing a fair game (that is, each bet has expected value zero to both sides) will eventually go broke against an opponent with infinite wealth.

* 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 for the unsurprising idea that a gambler playing a negative expected value game will eventually go broke, regardless of betting system. This is another corollary to Huygens' result.

While the first three meanings have some relevance for gamblers, they are also general theorems with wide application and many related results in probability and statistics. Huygens' result in particular led to important advances in the mathematical theory of probability.

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 \frac{Bankroll}{N} 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 (giving them higher denomination chips). 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 (if it is 1, then he is no gambler), 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 (with 0.5 probability of winning) will eventually either go broke or double his wealth. These events are equally likely, or the game would not be fair (ignoring the fact that his bankroll might jump over one event or the other, this is a minor complication to the argument). So he has a 0.5 chance of going broke before doubling his money. Once he doubles his money, he again has a 0.5 chance of doubling his money before going broke. Overall, there is a 0.25 chance that he will go broke after doubling his money once, but before doubling it twice. Continuing this way, his chance of going broke is 0.5 + 0.25 + 0.125 + . . . which approaches 1.

Huygens' 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' 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 100%. (One way to see this is as follows. Any given finite string of heads and tails will eventually be flipped with certainty: the probability of not seeing this string, while high at first, decays exponentially. In particular, the players would eventually flip a string of heads as long as the total number of pennies in play, by which time the game must have already ended.)

If player one has n1 pennies and player two n2 pennies, the chances P1 and P2 that players one and two, respectively, will end penniless are:

P_1= \frac{n_2}{n_1+n_2}

P_2= \frac{n_1}{n_1+n_2}

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 (P1) has 8 pennies and player two (P2) were to have 5 pennies then the probability of each losing is:

P_1=\frac{5}{8+5} =\frac{5}{13} = 0.3846 or 38.46%

P_2=\frac{8}{8+5} =\frac{8}{13} = 0.6154 or 61.54%

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 (in this case 6) the likelihood of each losing is:

P_1=\frac{6}{6+6} = \frac{6}{12} = \frac{1}{2} = 0.5

P_2=\frac{6}{6+6} = \frac{6}{12} = \frac{1}{2} =0.5

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:

P_1= \frac{(\frac{q}{p})^{n_1}-(\frac{q}{p})^{n_1+n_2}}{1-(\frac{q}{p})^{n_1+n_2}}

P_2= \frac{1-(\frac{q}{p})^{n_1}}{1-(\frac{q}{p})^{n_1+n_2}}

This can be shown as follows: Consider the probability of player 1 experiencing gamblers ruin having started with n > 1 amount of money, P(Rn). Then, using the Law of Total Probability, we have

P(R_n) = P(R_n|W)P(W) + P(R_n|\bar{W})P(\bar{W}),

where W denotes the event that player 1 wins the first bet. Then clearly P(W) = p and P(\bar{W}) = 1 - p = q. Also P(Rn | W) is the probability that player 1 experiences gambler's ruin having started with n + 1 amount of money: P(Rn + 1); and P(R_n | \bar{W}) is the probability that player 1 experiences gambler's ruin having started with n − 1 amount of money: P(Rn − 1).

Denoting qn = P(Rn), we get the linear homogenous recurrence relation

qn = qn + 1p + qn − 1q,

which we can solve using the fact that q0 = 1 (i.e. the probability of gambler's ruin given that player 1 starts with no money is 1), and q_{n_1 + n_2} = 0 (i.e. the probability of gambler's ruin given that player 1 starts with all the money is 0.) For a more detailed description of the method see e.g. Feller (1957).

N-player ruin problem

The above described problem (2 players) is a special case of the so-called N-Player ruin problem. Here N \geq 2 \, \, players with initial capital x_1, x_2, \cdots, x_N\,\, dollars, respectively, play a sequence of (arbitrary) 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 N = 3 \, and large initial capitals x_1, x_2, \cdots, x_N \, the solution can be well approximated by using two-dimensional Brownian motion. (For N > 3 this is not possible.) In practice the true problem is to find the solution for the typical cases of N \geq 3 and limited initial capital. Swan (2006) proposed an algorithm based on Matrix-analytic methods (Folding algorithm for ruin problems) which reduces, in such cases, the order of the computational task significantly.