Gambler's Ruin Problem Mathematical Proof

Gambler's ruin problem is a statistical concept that 2 people gamble $1 in each game, one of them will lose all his or her money if they keep gambling.

Problem Statement

Let A and B be gamblers who gamble 1$ in each game. A's probability of winning in each game is p while A’s probability of losing in each game is 1-p, Let 1-p be denoted as q. The sum of the probability of losing and the probability of wining is 1 because A either wins or loses a game. There are no other outcomes.

Let A have x amount of money and B have n-x amount of money. A and B have total amount of n dollars.

We want to find the probability of A wining all B's money if they keep gambling. Let it be P_x.

After One Game

A and B gamble for one game. A either wins with the probability of p or loses with the probability of q.

If A wins this game, A will have x+1 dollars and A’s probability of wining all B's money become P_x+1.

If A loses this game, A will have x-1 dollars and A’s probability of wining all B's money become P_x-1.

So together, P_x = p* P_x+1 + q*P_x-1.

P₀ = 0, because A has lost all his or her money and the game has ended.

P_n = 1, because A has won all B's money and the game has ended.

Guess the Answer First

Assume P_x = xⁱ. P_x = p* P_x+1 + q*P_x-1 becomes xⁱ = p*xⁱ⁺¹ + q* x^i-1, which is this quadratic equation: x = p*x² + q.

Solving for x, we get x = 1 or x = q/p.

Testing the results

If x = 1, P_x = xⁱ = 1, which does not satisfy the fact that P₀ = 0.

If x = q/p, for P_n to be 1, q will have to be p, then x will be 1 again.

Therefore, the solution will be some combination of the 2 roots of x, 1 and q/p .

Solving for this combination

Let P_x = A*(1)^x + B*(q/p)^x, which is the linear combination of the two roots of x,1 and q/p plugging into P_x = xⁱ.

Applying the results of P₀ = 0 and P_n = 1 to this linear combination, we get the following derivation:

P₀ = 0 = A + B, A = -B

P_n = 1 = A + B* (q/p)ⁿ = -B + B*(q/p)ⁿ = B((q/p)ⁿ - 1).
B = 1 / ((q/p)ⁿ - 1)

A = -B, so A = -1 / ((q/p)ⁿ - 1)

Finally, P_x = A*(1)^x + B*(q/p)^x = -1 / ((q/p)ⁿ - 1) + (q/p)^x / ((q/p)ⁿ - 1)

= (q/p)^x -1 / ((q/p)ⁿ - 1)

What If p = q?

If p = q, P_x = (q/p)^x -1 / ((q/p)ⁿ - 1) = 0/0 = 0, which doesn't make sense because P_n is 1 not 0 even if p = q.

As p approaches q, p/q goes to 1 then both (q/p)^x -1 and (q/p)ⁿ -1 go to 0. Then this has become a "0 over 0" problem, which can be solved by applying the L'hopital's rule.

By taking the first derivative of both (q/p)^x -1 and (q/p)ⁿ -1 with respect to (q/p), we get x(q/p)^x-1 and n(q/p)^n-1.

Plug back in P_x = (q/p)^x -1 / ((q/p)ⁿ - 1), we get

P_x = x(q/p)^x-1/ n(q/p)^n-1 = x / n when p goes to q.

Suggested reading: Probability Calculator: Gambler’s Ruin Problem