Gambler's ruin
The concept was initially stated: A persistent gambler who raises his bet to a fixed fraction of the gambler's bankroll after a win, but does not reduce it after a loss, will eventually and inevitably go broke, even if each bet has a positive expected value.
[1] Another statement of the concept is that a persistent gambler with finite wealth, playing a fair game (that is, each bet has expected value of zero to both sides) 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 probable that the gambler will, with virtual certainty, return to their point of origin, which means going broke, and is ruined an infinite number of times if the random walk continues forever.
This 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.
The term's common usage today is another corollary to Huygens's result.
However it also leads to mathematical theorems with wide application and many related results in probability and statistics.
Huygens's result in particular led to important advances in the mathematical theory of probability.
The earliest known mention of the gambler's ruin problem is a letter from Blaise Pascal to Pierre Fermat in 1656 (two years after the more famous correspondence on the problem of points).
[2] 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.
The winner is the first to reach twelve points; what are the relative chances of each player winning?
[5] The gambler's ruin problem is often applied to gamblers with finite capital playing against a bookie or casino assumed to have an “infinite” or much larger amount of capital available.
It can then be proven that the probability of the gambler's eventual ruin tends to 1 even in the scenario where the game is fair or what mathematically is defined as a martingale.
when they win, but do not reduce their stake when they lose (a not uncommon pattern among real gamblers).
It is not necessary that they follow the precise rule, just that they increase their bet fast enough as they win.
After each flip of the coin the loser transfers one penny to the winner.
If there are no other limitations on the number of flips, the probability that the game will eventually end this way is 1.
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.)
It follows that even with equal odds of winning the player that starts with fewer pennies is more likely to fail.
An argument is that the expected hitting time is finite and so with a martingale, associating the value
Alternately, this can be shown as follows: Consider the probability of player 1 experiencing gamblers ruin having started with
is the probability that player 1 experiences gambler's ruin having started with
is the probability that player 1 experiences gambler's ruin having started with
(i.e. the probability of gambler's ruin given that player 1 starts with no money is 1), and
(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 (1970), An introduction to probability theory and its applications, 3rd ed.
Standard Markov chain methods can be applied to solve this more general problem in principle, but the computations quickly become prohibitive as soon as the number of players or their initial capitals increase.
In practice the true problem is to find the solution for the typical cases of
Swan (2006) proposed an algorithm based on matrix-analytic methods (Folding Algorithm for ruin problems) which significantly reduces the order of the computational task in such cases.
