The gambler’s ruin problem

This post discusses the problem of the gambler’s ruin. We start with a simple illustration.

Two gamblers, A and B, are betting on the tosses of a fair coin. At the beginning of the game, player A has 1 coin and player B has 3 coins. So there are 4 coins between them. In each play of the game, a fair coin is tossed. If the result of the coin toss is head, player A collects 1 coin from player B. If the result of the coin toss is tail, player A pays player B 1 coin. The game continues until one of the players has all the coins (or one of the players loses all his/her coins). What is the probability that player A ends up with all the coins?

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.

    \begin{array}{ccccccc}    \text{Game} &  \text{ } & \text{Coin Tosses} &  \text{ } & \text{Coins of Player A}  & \text{ } & \text{Coins of Player B}  \\    \text{ } &   \text{ } & \text{ } & \text{ } & \text{ } &  \\   \text{ } &   \text{ }& \text{ } &   \text{ } & 1 &  & 3  \\   1 &   \text{ }& H &   \text{ } & 2 &  & 2  \\   \text{ } &   \text{ }& T &   \text{ } & 1 &  & 3  \\  \text{ } &   \text{ }& H &   \text{ } & 2 &  & 2  \\   \text{ } &   \text{ }& H &   \text{ } & 3 &  & 1  \\   \text{ } &   \text{ }& H &   \text{ } & 4 &  & 0  \\       \end{array}

In the first simulation, player A got lucky with 4 heads in 5 tosses. The following shows the next simulation.

    \begin{array}{ccccccc}    \text{Game} &  \text{ } & \text{Coin Tosses} &  \text{ } & \text{Coins of Player A}  & \text{ } & \text{Coins of Player B}  \\    \text{ } &   \text{ } & \text{ } & \text{ } & \text{ } &  \\   \text{ } &   \text{ }& \text{ } &   \text{ } & 1 &  & 3  \\   2 &   \text{ }& H &   \text{ } & 2 &  & 2  \\   \text{ } &   \text{ }& H &   \text{ } & 3 &  & 1  \\  \text{ } &   \text{ }& T &   \text{ } & 2 &  & 2  \\   \text{ } &   \text{ }& H &   \text{ } & 3 &  & 1  \\   \text{ } &   \text{ }& H &   \text{ } & 4 &  & 0  \\        \end{array}

Player A seems to be on a roll. Here’s the results of the next two simulated games.

    \begin{array}{ccccccc}    \text{Game} &  \text{ } & \text{Coin Tosses} &  \text{ } & \text{Coins of Player A}  & \text{ } & \text{Coins of Player B}  \\    \text{ } &   \text{ } & \text{ } & \text{ } & \text{ } &  \\   \text{ } &   \text{ }& \text{ } &   \text{ } & 1 &  & 3  \\   3 &   \text{ }& T &   \text{ } & 0 &  & 4  \\    \text{ } &   \text{ } & \text{ } & \text{ } & \text{ } &  \\   \text{ } &   \text{ }& \text{ } &   \text{ } & 1 &  & 3  \\   4 &   \text{ }& H &   \text{ } & 2 &  & 2  \\  \text{ } &   \text{ }& T &   \text{ } & 1 &  & 3  \\   \text{ } &   \text{ }& T &   \text{ } & 0 &  & 4  \\           \end{array}

Now player A loses both of these games. For good measure, we show one more simulation.

    \begin{array}{ccccccc}    \text{Game} &  \text{ } & \text{Coin Tosses} &  \text{ } & \text{Coins of Player A}  & \text{ } & \text{Coins of Player B}  \\    \text{ } &   \text{ } & \text{ } & \text{ } & \text{ } &  \\   \text{ } &   \text{ }& \text{ } &   \text{ } & 1 &  & 3  \\   5 &   \text{ }& H &   \text{ } & 2 &  & 2  \\   \text{ } &   \text{ }& H &   \text{ } & 3 &  & 1  \\  \text{ } &   \text{ }& T &   \text{ } & 2 &  & 2  \\   \text{ } &   \text{ }& H &   \text{ } & 3 &  & 1  \\   \text{ } &   \text{ }& T &   \text{ } & 2 &  & 2  \\    \text{ } &   \text{ }& H &   \text{ } & 3 &  & 1  \\  \text{ } &   \text{ }& T &   \text{ } & 2 &  & 2  \\   \text{ } &   \text{ }& T &   \text{ } & 1 &  & 3  \\   \text{ } &   \text{ }& T &   \text{ } & 0 &  & 4  \\      \end{array}

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
    \begin{array}{ccccccc}    \text{Simulated} &  \text{ } & \text{Player A} &  \text{ } & \text{Player B}  & \text{ } & \text{Total}  \\  \text{Runs} &  \text{ } & \text{Winning} &  \text{ } & \text{Winning}  & \text{ } & \text{ }  \\  \text{ } &  \text{ } & \text{Frequency} &  \text{ } & \text{Frequency}  & \text{ } & \text{ }  \\    \text{ } &   \text{ } & \text{ } & \text{ } & \text{ } &  \\   1 &   \text{ }& 23 &   \text{ } & 77 &  & 100  \\   2 &   \text{ }&34 &   \text{ } & 66 &  & 100  \\   3 &   \text{ }& 19 &   \text{ } & 81 &  & 100  \\  4 &   \text{ }& 24 &   \text{ } & 76 &  & 100  \\   5 &   \text{ }& 27 &   \text{ } & 73 &  & 100  \\   6 &   \text{ }& 22 &   \text{ } & 78 &  & 100  \\   7 &   \text{ }& 21 &   \text{ } & 79 &  & 100  \\  8 &   \text{ }& 24 &   \text{ } & 76 &  & 100  \\  9 &   \text{ }& 28 &   \text{ } & 72 &  & 100  \\  10 &   \text{ }& 24 &   \text{ } & 76 &  & 100  \\  \text{ } &   \text{ } & \text{ } & \text{ } & \text{ } &  \\  \text{Total} &   \text{ }& 246 &   \text{ } & 754 &  & 1000  \\    \end{array}

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

Two gamblers, A and B, are betting on the tosses of a fair coin. At the beginning of the game, player A has n_1 coins and player B has n_2 coins. So there are n_1+n_2 coins between them. In each play of the game, a fair coin is tossed. If the result of the coin toss is head, player A collects 1 coin from B. If the result of the coin toss is tail, player A pays B 1 coin. The game continues until one of the players has all the coins. What is the probability that player A ends up with all the coins? What is the probability that player B ends up with all the coins?

Solution: Gambler’s Ruin Problem

The long run probability of player A winning all the coins is \displaystyle P_A=\frac{n_1}{n_1+n_2}.
The long run probability of player B winning all the coins is \displaystyle P_B=\frac{n_2}{n_1+n_2}.

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 p be the probability that the coin toss results in a head. Let q=1-p. Suppose that there are n coins initially between player A and player B.

Let A_i be the probability that player A will own all the n coins when player A starts the game with i coins and player B starts with n-i coins. On the other hand, let B_i be the probability that player B will own all the n coins when player A starts the game with i coins and player B starts with n-i coins.

The goal here is to derive expressions for both A_i and B_i for i=1,2,\cdots,n-1 and to show that A_i+B_i=1. 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 A_0=0 and A_n=1 as well as B_0=0 and B_n=1. In the following derivation, H is the event that the first toss is a head and T is the event that the first toss is a tail.

Let E be the event that player A owning all the coins when player A starts the game with i coins and player B starts with n-i coins, i.e. A_i=P(E). First condition on the outcome of the first toss of the coin.

    \displaystyle \begin{aligned} A_i&=P(E | H) \ P(H)+P(E | T) \ P(T) \\&=P(E | H) \ p+P(E | T) \ q  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1) \end{aligned}

Consider the conditional probabilities P(E | H) and P(E | T). Note that P(E | H)=A_{i+1}. If the first toss is a head, then player A has i+1 coins and player B would have n-(i+1) 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 i+1 coins. Similarly, P(E | T)=A_{i-1}. Plug these into (1), we have:

    A_i=p \ A_{i+1}+q \ A_{i-1} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Further derivation can be made on equation (2).

    A_i=p \ A_i+ q \ A_i=p \ A_{i+1}+q \ A_{i-1}

    p \ A_{i+1}-p \ A_i=q \ A_i - q \ A_{i-1}

    \displaystyle A_{i+1}-A_{i}=\frac{q}{p} \ (A_i-A_{i-1}),\ \ \ \ i=1,2,3,\cdots,n-1

Plugging in the values 1,2,3,\cdots,n-1 for i produces the following n-1 equations.

    \displaystyle \begin{aligned} &A_{2}-A_{1}=\frac{q}{p} \ (A_1-A_{0})=\frac{q}{p} \ A_1 \\&A_{3}-A_{2}=\frac{q}{p} \ (A_2-A_{1})=\bigg[ \frac{q}{p} \biggr]^2 \ A_1 \\&\ \ \ \cdots \\&A_{i}-A_{i-1}=\frac{q}{p} \ (A_{i-1}-A_{i-2})=\bigg[ \frac{q}{p} \biggr]^{i-1} \ A_1 \\&\ \ \ \cdots \\&A_{n}-A_{n-1}=\frac{q}{p} \ (A_{n-1}-A_{n-2})=\bigg[ \frac{q}{p} \biggr]^{n-1} \ A_1 \end{aligned}

Adding the first i-1 equations produces the following equations.

    \displaystyle A_i-A_1=A_1 \ \biggl[\frac{q}{p}+\bigg( \frac{q}{p} \biggr)^{2}+\cdots+\bigg( \frac{q}{p} \biggr)^{i-1} \biggr]

    \displaystyle A_i=A_1 \ \biggl[1+\frac{q}{p}+\bigg( \frac{q}{p} \biggr)^{2}+\cdots+\bigg( \frac{q}{p} \biggr)^{i-1} \biggr] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

There are two cases to consider. Either \frac{q}{p}=1 or \frac{q}{p} \ne 1. The first case means p=\frac{1}{2} and the second case means p \ne \frac{1}{2}. The following is an expression for A_i for the two cases.

    \displaystyle  A_i = \left\{ \begin{array}{ll}           \displaystyle  i \ A_1 &\ \ \ \ \ \ \displaystyle \frac{q}{p}=1 \\            \text{ } & \text{ } \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4) \\          \displaystyle  \frac{ \displaystyle 1- \biggl(\frac{q}{p} \biggr)^i}{\displaystyle 1-\frac{q}{p}} A_1 &\ \ \ \ \ \ \displaystyle \frac{q}{p} \ne 1            \end{array} \right.

The above two-case expression for A_i is applicable for i=2,3,\cdots,n. Plugging n into i with A_n=1 gives the following expression for A_1:

    \displaystyle  A_1 = \left\{ \begin{array}{ll}           \displaystyle  \frac{1}{n} &\ \ \ \ \ \ p=\frac{1}{2} \\            \text{ } & \text{ } \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (5) \\          \displaystyle  \frac{\displaystyle 1-\frac{q}{p}}{1-\biggl( \displaystyle\frac{q}{p} \biggr)^n} &\ \ \ \ \ \ p \ne \frac{1}{2}            \end{array} \right.

Plugging A_1 from (5) into (4) gives the following:

    \displaystyle  A_i = \left\{ \begin{array}{ll}           \displaystyle  \frac{i}{n} &\ \ \ \ \ \ p=\frac{1}{2} \\            \text{ } & \text{ } \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6) \\          \displaystyle  \frac{1-\biggl( \displaystyle \frac{q}{p} \biggr)^i}{1-\biggl( \displaystyle \frac{q}{p} \biggr)^n} &\ \ \ \ \ \ p \ne \frac{1}{2}            \end{array} \right.

The expression for A_i in (6) is applicable for i=1,2,\cdots,n. For the case of p=\frac{1}{2}, 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 B_i is the probability that player B will end up owning all the coins when initially player A has i coins and player B has n-i coins. By symmetry, the following gives the expression for B_i.

    \displaystyle  B_i = \left\{ \begin{array}{ll}           \displaystyle  \frac{n-i}{n} &\ \ \ \ \ \ q=\frac{1}{2} \\            \text{ } & \text{ } \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7) \\          \displaystyle  \frac{1- \biggl(\displaystyle \frac{p}{q} \biggr)^{n-i}}{\displaystyle 1- \biggl(\frac{p}{q} \biggr)^n} &\ \ \ \ \ \ q \ne \frac{1}{2}            \end{array} \right.

For the case p=\frac{1}{2}, which is equivalent to q=\frac{1}{2}, it is clear that A_i+B_i=1. For the case p \ne \frac{1}{2}, the following shows that A_i+B_i=1.

    \displaystyle \begin{aligned} A_i+B_i&=\frac{1-\biggl( \displaystyle \frac{q}{p} \biggr)^i}{1-\biggl( \displaystyle \frac{q}{p} \biggr)^n}+\frac{1- \biggl(\displaystyle \frac{p}{q} \biggr)^{n-i}}{\displaystyle 1- \biggl(\frac{p}{q} \biggr)^n} \\&\text{ } \\&=\frac{p^n-p^n\biggl( \displaystyle \frac{q}{p} \biggr)^i}{p^n-q^n}+\frac{q^n- q^n \biggl(\displaystyle \frac{p}{q} \biggr)^{n-i}}{\displaystyle q^n- p^n}\\&\text{ } \\&=\frac{p^n-p^{n-i} \ q^i}{p^n-q^n}-\frac{q^n- q^i \ p^{n-i}}{\displaystyle p^n- q^n} \\&\text{ } \\&=\frac{p^n-q^n}{p^n-q^n}=1  \end{aligned}

The fact that A_i+B_i=1 shows that the gambling game discussed here has to end after certain number of plays and that it will not continue indefinitely.

___________________________________________________________________________

Further Discussion

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.

___________________________________________________________________________
\copyright 2017 – Dan Ma

Advertisements

7 thoughts on “The gambler’s ruin problem

  1. Pingback: The probability of breaking the bank | Introductory Statistics

  2. Pingback: The gambler’s ruin – A world of ideas

  3. Pingback: The gambler’s ruin – Site Title

  4. Pingback: Five probability problems to help us think better | Math in the Spotlight

  5. Pingback: A walk down Random Lane | Topics in Probability

  6. Pingback: More on random walks | Topics in Probability

  7. Pingback: A first look at applications of Markov chains | Topics in Probability

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s