THE CHINESE UNIVERSITY OF HONG KONG

Department of Mathematics
MATH3280
Introductory Probability
Jeff Chak-Fu WONG

GAMBLER’S RUIN PROBLEM

If you find any errors/typos, please email me at:

jwong@math.cuhk.edu.hk

The Gambler’s Ruin problem calculates a gambler’s winning proba-

bility given these conditions:

(1) Both players begin with a set amount of money.

(2) The winning probability for each player remains constant.
(3) The game ends when one player loses all their money.
Example 1. (Motivating Example)
Consider two gamblers, Robert and Mary, starting with $100 and
$60 respectively. They bet on successive coin tosses. If the coin lands
heads, Robert wins $1 from Mary. Otherwise, Mary wins $1 from
Robert. The game continues until one player loses all their money.
The coin is biased, with a 1/3 probability of landing heads. We aim
to determine Robert’s winning probability.
Before solving, note the following:

(1) We can’t predict the number of turns to end the game. Mary
could lose all 60 games. Alternatively, the game might never end
if they keep winning alternately. Both scenarios, though unlikely,
are possible, as are infinite other outcomes.
1
2 GAMBLER’S RUIN PROBLEM

(2) In Statistics, identifying the problem invariant is crucial. This is a

constant element that doesn’t change or depend on sub-problem
outcomes. In our case, the invariant is the total money the gam-
blers have, which always equals $100 + $60 = $160. The only
variable is each gambler’s money. This allows us to track one
gambler’s money at any time. We can find the other’s by sub-
tracting from the total. For example, if Robert has $85, Mary
has $160 - $85 = $75. Note, this may not apply to all problem
variants, which we’ll discuss later.
(3) Problems like these are often modeled using Markov Chain mod-
els. However, in this note, we’ll simplify the approach using con-
ditional probability and some modeling techniques. The central
idea is to extend the game into the past and future to account for
various possibilities. We’ll explore how to do this later.
 GAMBLER’S RUIN PROBLEM 3

Let’s start by defining some events:

(1) Let R100 denote the event that Robert wins the game given that
he starts with $100. Note that due to invariance, we don’t need
to track Mary’s starting amount.
(2) Let H denote the event that the coin lands heads on the first flip.
(3) Let T denote the event that the coin lands tails on the first flip.
With these definitions, we can define P (R100), the probability that
Robert wins the game, given that he starts with $100, by conditioning
it on the outcome of the first flip:
P (R100) = P (R100|H)P (H) + P (R100|T )P (T )
1 2
= P (R100|H) × + P (R100|T ) ×
3 3
We note that if Robert wins the first game, he ends up with $101.
This is equivalent to Robert starting the game with $101. Similarly, if
Robert loses the first game, he ends up with $99, which is equivalent
to him starting the game with $99. Thus, we have:

1 2
P (R100) = P (R100|H) × + P (R100|T ) ×
3 3
1 2
= P (R101) × + P (R99) ×
3 3
We have obtained a recurrence relationship. The probability of Robert
winning, given that he starts with $100, is defined recursively in terms
of the probabilities of him winning given that he starts with $101 and
$99. The remaining task is to solve this recurrence relation. To do this,
we need to extend the problem backward and/or forward in time until
we reach a base condition, i.e., some i such that P (Ri) is known to us.
4 GAMBLER’S RUIN PROBLEM

There are two base conditions that can help us solve this recursive
problem:

(1) If Robert started with $0, the probability that Robert wins should
be 0. This is because if Robert had no money to start with, he
has already lost the game.
(2) If Robert started with $160, the probability that Robert wins
should be 1. This is because if Robert had all the money to start
with, he has already won the game.

Thus, we have the following pieces of information:


P (R101) 2P (R99)
P (R100) = +


3 3
 P (R0) =0

P (R160) = 1


Prior to resolving this recursive problem, we reformulate the recur-

rence relation in a subtly distinct manner to streamline our solution:

P (R101) 2P (R99)
P (R100) = +
3 3

=⇒ P (R101) = 3P (R100) − 2P (R99)

=⇒ P (R101)−P (R100) = 3P (R100)−P (R100) − 2P (R99)

= 2(P (R100) − P (R99))
 GAMBLER’S RUIN PROBLEM 5

=⇒ P (Ri+1) − P (Ri) = 2(P (Ri) − P (Ri−1))

Having established the recurrence relation and the base condition, we

can solve the recurrence formula by tracing the progression of the game
both backward and forward in time. Remarkably, this yields:

i=1: P (R2) − P (R1) = 2(P (R1) − P (R0))

i=2: P (R3) − P (R2) = 2(P (R2) − P (R1))
i=3: P (R4) − P (R3) = 2(P (R3) − P (R2))
i=4: P (R5) − P (R4) = 2(P (R4) − P (R3))
...
i = 99 : P (R100) − P (R99) = 2(P (R99) − P (R98))
i = 100 : P (R101) − P (R100) = 2(P (R100) − P (R99))
...
i = 158 : P (R159) − P (R158) = 2(P (R158) − P (R157))
i = 159 : P (R160) − P (R159) = 2(P (R159) − P (R159))

We have chosen the value of i to range from 1 to 159 because our

recurrence relations allow for:

• a maximum value of i+1 = 159+1 = 160 (the maximum amount

Robert can have) and
• a minimum value of i − 1 = 1 − 1 = 0 (the minimum amount
Robert can have).
6 GAMBLER’S RUIN PROBLEM

We substitute the base case solutions at 0 and 160, yielding the fol-
lowing results:

i = 1 : P (R2) − P (R1) = 2(P (R1) − P (R0)) = 2P (R1)

i = 2 : P (R3) − P (R2) = 2(P (R2) − P (R1)) = 22P (R1)
i = 3 : P (R4) − P (R3) = 2(P (R3) − P (R2)) = 23P (R1)
i = 4 : P (R5) − P (R4) = 2(P (R4) − P (R3)) = 24P (R1)
...

i = 99 : P (R100) − P (R99) = 2(P (R99) − P (R98)) = 299P (R1)

i = 100 : P (R101) − P (R100) = 2(P (R100) − P (R99)) = 2100P (R1)
...

i = 158 : P (R159) − P (R158) = 2(P (R158) − P (R157)) = 2158P (R1)

i = 159 : P (R160) − P (R159) = 2(P (R159) − P (R158)) = 2159P (R1)

If we add the first 99 equations (1 ≤ i ≤ 99), we get:

P (R2) − P (R1) + P (R3) − P (R2) + · · · + P (R100) − P (R99)
= 2P (R1) + 22P (R1) + 23P (R1) + · · · + 299P (R1)

=⇒ P (R100) − P (R1) = P (R1) 2 + 22 + · · · + 299

2(299 − 1)
= P (R1) = (2100 − 2)P (R1)
2−1
 GAMBLER’S RUIN PROBLEM 7

(1) =⇒ P (R100) = (2100 − 1)P (R1)

Observe how the formulation of the recurrence relation enables us to

eliminate all terms, leaving us with merely two. Additionally, note that
we have employed the formula for a geometric series to compute the
sum of powers of two. Now, if we ascertain P (Ri), we can calculate
P (R100), thereby resolving our problem! To determine P (Ri), we sum
all 159 equations previously shown and apply the second base condition
that P (R160) = 1 :

P (R2) − P (R1) + P (R3) − P (R2) + · · · + P (R160) − P (R159)

= 2P (R1) + 22P (R1) + 23P (R1) + · · · + 2159P (R1)

=⇒ P (R160) − P (R1) = P (R1) 2 + 22 + · · · + 2159

2(2159 − 1)
= P (R1) = (2160 − 2)P (R1)
2−1

(2) =⇒ P (R160) = (2160 − 1)P (R1)

P (R160) 1
(3) =⇒ P (R1) = =
2160 − 1 2160 − 1

Substituting this result into equation (4), we get:

8 GAMBLER’S RUIN PROBLEM

2100 − 1
(4) =⇒ P (R100) = 160 ≈ 8.673617 × 10−19
2 −1

Some may find the outcome surprising given that Robert commenced
with a significantly larger amount. However, upon recognizing that
Robert’s odds of winning are approximately half those of Mary at
each game, one quickly comprehends why the probability values com-
mence an exponential decay, culminating in an almost zero probability
of Robert winning the game.
Indeed, one can generalize the aforementioned formula, assuming that
Robert initiates with an amount $C, and Mary commences with an
amount $D. If the probability of heads is denoted as α, then the recur-
rence relation and base cases would be defined as follows:


P (RC )
 = αP (RC+1) + (1 − α)P (RC−1)
P (R0) =0

P (R
C+D ) = 1

Resolving the aforementioned recurrence formula in a similar manner

as before yields the following solution to the generalized Gambler’s Ruin
problem:

 C
1−α
−1
α
P (RC ) =  C+D
1−α
−1
α
 GAMBLER’S RUIN PROBLEM 9

Observe that the preceding equations are valid only when α ̸= 0.5.
If α = 0.5, the problem simplifies considerably, as the gambler with
a larger sum of money is more likely to win, given that their winning
probabilities for each game are identical. In such a scenario, the solution
would trivially be

C
P (RC ) =
C +D
■
10 GAMBLER’S RUIN PROBLEM

In the gambler’s ruin problem, there are only 2 gamblers, but they
are not assumed to be of equal skill.
Example 2. The generalized gambler’s ruin problem

Two gamblers, A and B, bet on the outcomes of successive flips of a

coin.

On each flip, if the coin comes up heads, A collects 1 unit from B,

whereas if it comes up tails, A pays 1 unit to B.

They continue to do this until one of them runs out of money (gets
ruined).

Assuming that the successive flips of the coin are independent and
each flip results in a head with probability p, what is the probability
that A ends up with all the money if he starts with i units and B starts
with N − i units?

Figure 1. Set n = N

Solution

Let p be the probability that the coin toss results in a head. Let
q = 1 − p. Assume that there are N units initially between Gambler
A and Gambler B.
 GAMBLER’S RUIN PROBLEM 11

In each round A wins 1 unit with probability p or loses 1 unit with

probability q = 1 − p (equivalently, in each round B wins 1 unit with
probability q = 1 − p and losses 1 unit with probability p.)

Let Pi be the probability that Gambler A will own all the N units
when Gambler A starts the game with i units and Gambler B starts
with N − i units. Conversely, let Qi be the probability that Gambler
B will own all the N units when Gambler A starts the game with i
units and Gambler B starts with N − i units.

The goal here is to derive expressions for both Pi and Qi for i =

1, 2, · · · , N − 1 and to show that Pi + Qi = 1. The latter point, while
seemingly intuitive, is not entirely trivial. It essentially states that the
game will conclude in a finite number of moves (it cannot continue
indefinitely).

Let E denote the event that A ends up with all the money when he
starts with i and B start with N − i. To clarify the dependence on the
initial fortune of A, let Pi = P (E).

We shall obtain an expression for P (E) by conditioning on the out-

come of the first flip as follows:

Let H denote the event that the first flip lands on heads, and H c
denote the event that the first flip is a tail. Then, we have:
Pi = P (E)
= P (E|H)P (H) + P (E|H c)P (H c)
= pP (E|H) + (1 − p)P (E|H c)
Now, given that the first flip lands on heads, the situation after the first
bet is that A has i + 1 units and B has N − (i + 1) since the successive
12 GAMBLER’S RUIN PROBLEM

flips are assumed to be independent. With a common probability p of

heads, it follows that, from that point on, A’s probability of winning
all the money is exactly the same as if the game were just starting with
A having an initial fortune of i + 1 and B having an initial fortune of
N − (i + 1) Therefore,
P (E|H) = Pi+1
and similarly,
P (E|H c) = Pi−1
Hence, (letting q = 1 − p,) we obtain
(5) Pi = pPi+1 + qPi−1, i = 1, 2, . . . , N − 1
By making use of the obvious boundary conditions P0 = 0 and PN = 1,
we can now solve Equation (5). To be more precise, we have

0
 if i = 0
Pi = pPi+1 + qPi−1 if 0 < i < N

1 if i = N

Here, P0 = 0 is the probability that the gambler will win given that
he starts off broke and PN = 1 is the probability he will win if he starts
off with his target amount. Otherwise, since our moves are independent
of the past, with probability p we obtain i + 1 dollars with probability
1 − p we obtain i − 1 units. This gives the recurrence.
Since p + q = 1, these equations are equivalent to
1 · Pi = pPi+1 + qPi−1
or
(p + q)Pi = pPi+1 + qPi−1
or
pPi + qPi = pPi+1 + qPi−1
 GAMBLER’S RUIN PROBLEM 13

or
pPi+1 − pPi = qPi − qPi−1
or
q
(6) Pi+1 − Pi = (Pi − Pi−1) i = 1, 2, . . . , N − 1
p
Hence, since P0 = 0, we obtain, from Equation (6),

= pq (P1 − P0) = pq P1


P2 − P1

    2
P3 − P 2 = p (P2 − P1) = p p P1 = pq P1
q q q





  2  3
= p (P3 − P2) = p p P1 = pq P1
q q q

P4 − P3



(7) ...
  i−1
= p (Pi−1 − Pi−2) = pq
q

Pi − Pi−1 P1




...





  N −1

PN − PN −1 = p (PN −1 − PN −2) = pq
q
P1


Adding the first i − 1 equations of (7) yields

"     i−1#
2
q q q
Pi − P1 = P 1 + + ··· +
p p p
or "   
2  i−1#
q q q
Pi = P1 + + ··· +
p p p
or "    2  i−1#
q q q
Pi = P1 1+ + + ··· +
p p p
14 GAMBLER’S RUIN PROBLEM

The formula for the sum of the first i terms of a geometric series is:
i−1  i

X 1−r
ari = a 1 + r + r2 + · · · + rn−1 = a


, if r ̸= 1.
i=0
1 − r

q
Therefore, if r = p ̸= 1, we have
1 − (q/p)i q
Pi = P1 if ̸= 1
1 − (q/p) p
q
In case r = p = 1, we have
q
Pi = P1 [1 + 1 + · · · + 1] = iP1 if = 1
| {z } p
i terms
and thus
1−(q/p)i
(
q
1−(q/p) P1 if p ̸= 1
Pi = q
.
iP1 if p =1

Choosing i = N and using the fact that PN = 1 yields

1−(q/p)N
(
P if p ̸= q
1 = PN = 1−(q/p) 1 .
N P1 if p = q = 1/2
( 1−(q/p) 1
1−(q/p)N
if p ̸= 2
P1 = 1
.
N if p = q = 1/2

Hence,
1−(q/p)i  1−(q/p)i
(
1−(q/p)


1
1−(q/p)

1−(q/p)N
= 1−(q/p)N
if p ̸= 2
(8) Pi =  
.
i N1 = Ni if p = q = 1/2
 GAMBLER’S RUIN PROBLEM 15

The expression for Pi in (8) is applicable for i = 1, 2, · · · , N . In the

case of p = 21 , the probability of Gambler A owning all the units is the
ratio of the initial number of units of Gambler A to the total number
of units, which is identical to what was stated earlier. Recall that Qi is
the probability that Gambler B will end up owning all the units when
initially Gambler A has i units and Gambler B has N − i units. Then,
by symmetry to the situation described, and on replacing p by q and i
by N − i, it follows that

1−(p/q)N −i
(
1
1−(p/q)N
if q ̸= 2
Qi = N −i 1
.
N if q = 2

1
Moreover, since q = 2 is equivalent to p = 12 , we have, when q ̸= 12 ,

1 − (q/p)i 1 − (p/q)N −i
Pj + Qj = +
1 − (q/p)N 1 − (p/q)N
pN − pN (q/p)i q N − q N (p/q)N −i
= +
pN − q N q N − pN
pN − pN −iq i − q N + q ipN −i
=
pN − q N
pN − q N
= N
p − qN
=1

This result also holds when p = q = 12 , so

Pj + Qj = 1.
16 GAMBLER’S RUIN PROBLEM

In other words, this equation states that, with probability of 1, either

A or B will wind up with all of the money. In other words, the prob-
ability that the game continues indefinitely with A’s fortune always
being between 1 and N − 1 is zero.