1 Gambler’s Ruin Problem
Consider a gambler who starts with an initial fortune of $1 and then on each successive gamble
either wins $1 or loses $1 independent of the past with probabilities p and q = 1−p respectively.
Let R
n
denote the total fortune after the n
th
gamble. The gambler’s objective is to reach a total
fortune of $N, without first getting ruined (running out of money). If the gambler succeeds,
then the gambler is said to win the game. In any case, the gambler stops playing after winning
or getting ruined, whichever happe ns first. There is nothing special about starting with $1,
more generally the gambler starts with $i where 0 < i < N .
While the game proceeds, {R
n
: n ≥ 0} forms a simple random walk
R
n
= ∆
1
+ · · · + ∆
n
, R
0
= i,
where {∆
n
} forms an i.i.d. sequence of r.v.s. distributed as P (∆ = 1) = p, P (∆ = −1) = q =
1 − p, and represents the earnings on the succesive gambles.
Since the game stops when either R
n
= 0 or R
n
= N, let
τ
i
= min{n ≥ 0 : R
n
∈ {0, N}|R
0
= i},
denote the time at which the game s tops when R
0
= i. If R
τ
i
= N , then the gambler wins, if
R
τ
i
= 0, then the gambler is ruined.
Let P
i
= P (R
τ
i
= N) denote the probability that the gambler wins when R
0
= i. Clearly
P
0
= 0 and P
N
= 1 by definition, and we next proceed to compute P
i
, 1 ≤ i ≤ N − 1.
The key idea is to condition on the outcome of the first gamble, ∆
1
= 1 or ∆
1
= −1, yielding
P
i
= pP
i+1
+ qP
i−1
. (1)
The derivation of this recursion is as follows: If ∆
1
= 1, then the gambler’s total fortune
increases to R
1
= i+1 and so by the Markov property the gambler will now win with probability
P
i+1
. Similarly, if ∆
1
= −1, then the gambler’s fortune decreases to R
1
= i − 1 and so
by the Markov property the gambler will now win with probability P
i−1
. The probabilities
corresponding to the two outcomes are p and q yielding (1). Since p + q = 1, (1) can be
re-written as pP
i
+ qP
i
= pP
i+1
+ qP
i−1
, yielding
P
i+1
− P
i
=
q
p
(P
i
− P
i−1
).
In particular, P
2
− P
1
= (q/p)(P
1
− P
0
) = (q/p)P
1
(since P
0
= 0), so that
P
3
− P
2
= (q/p)(P
2
− P
1
) = (q/p)
2
P
1
, and more generally
P
i+1
− P
i
= (
q
p
)
i
P
1
, 0 < i < N.
Thus
P
i+1
− P
1
=
i
X
k=1
(P
k+1
− P
k
)
=
i
X
k=1
(
q
p
)
k
P
1
,
1
yielding
P
i+1
= P
1
+ P
1
i
X
k=1
(
q
p
)
k
= P
1
i
X
k=0
(
q
p
)
k
=
P
1
1−(
q
p
)
i+1
1−(
q
p
)
, if p 6= q;
P
1
(i + 1), if p = q = 0.5.
(2)
(Here we are using the “geometric series” equation
P
i
n=0
a
i
=
1−a
i+1
1−a
, for any number a and
any integer i ≥ 1.)
Choosing i = N − 1 and using the fact that P
N
= 1 yields
1 = P
N
=
P
1
1−(
q
p
)
N
1−(
q
p
)
, if p 6= q;
P
1
N, if p = q = 0.5,
from which we conclude that
P
1
=
1−
q
p
1−(
q
p
)
N
, if p 6= q;
1
N
, if p = q = 0.5,
thus obtaining from (2) (after algebra) the solution
P
i
=
1−(
q
p
)
i
1−(
q
p
)
N
, if p 6= q;
i
N
, if p = q = 0.5.
(3)
(Note that 1 − P
i
is the probability of ruin.)
1.1 Becoming infinitely rich or getting ruined
If p > 0.5, then
q
p
< 1 and thus from (3)
lim
N→∞
P
i
= 1 − (
q
p
)
i
> 0, p > 0.5. (4)
If p ≤ 0.5, then
q
p
≥ 1 and thus from (3)
lim
N→∞
P
i
= 0, p ≤ 0.5. (5)
To interpret the meaning of (4) and (5), suppose that the gambler starting with X
0
= i
wishes to continue gambling forever until (if at all) ruined, with the intention of earning as
much money as possible. So there is no winning value N; the gambler will only stop if ruined.
What will happen?
(4) says that if p > 0.5 (each gamble is in his favor), then there is a positive probability
that the gambler will never get ruined but instead will become infinitely rich.
(5) says that if p ≤ 0.5 (each gamble is not in his favor), then with probability one the
gambler will get ruined.
2
Examples
1. John starts with $2, and p = 0.6: What is the probability that John obtains a fortune of
N = 4 without going broke?
SOLUTION i = 2, N = 4 and q = 1 − p = 0.4, so q/p = 2/3, and we want
P
2
=
1 − (2/3)
2
1 − (2/3)
4
= 0.91
2. What is the probability that John will becom e infinitely rich?
SOLUTION
1 − (q/p)
i
= 1 − (2/3)
2
= 5/9 = 0.56
3. If John instead started with i = $1, what is the probability that he would go broke?
SOLUTION
The probability he becomes infinitely rich is 1−(q/p)
i
= 1−(q/p) = 1/3, so the probability
of ruin is 2/3.
1.2 Applications
Risk insurance business
Consider an insurance company that earns $1 per day (from interest), but on each day, indepen-
dent of the past, might suffe r a claim against it for the amount $2 with probability q = 1 − p.
Whenever such a claim is suffered, $2 is removed from the reserve of money. Thus on the
n
th
day, the net income for that day is exactly ∆
n
as in the gamblers’ ruin problem: 1 with
probability p, −1 with probability q.
If the insurance company starts off initially w ith a reserve of $i ≥ 1, then what is the
probability it will eventually get ruined (run out of money)?
The answer is given by (4) and (5): If p > 0.5 then the probability is given by (
q
p
)
i
> 0,
whereas if p ≤ 0.5 ruin will always ocurr. This makes intuitive sense because if p > 0.5, then
the average net income per day is E(∆) = p − q > 0, whereas if p ≤ 0.5, then the average net
income per day is E(∆) = p − q ≤ 0. So the c ompany can not expect to stay in business unless
earning (on average) more than is taken away by claims.
1.3 Random walk hitting probabilities
Let a > 0 and b > 0 be integers, and let R
n
denote a simple random walk with R
0
= 0. Let
p(a) = P (R
n
hits level a be fore hitting level −b).
By letting a = N − i and b = i (so that N = a + b), we can imagine a gambler who starts
with i = b and wishes to reach N = a+b before going broke. So we can compute p(a) by casting
the problem into the framework of the gamblers ruin problem: p(a) = P
i
where N = a + b,
i = b . Thus
3
p(a) =
1−(
q
p
)
b
1−(
q
p
)
a+b
, if p 6= q;
b
a+b
, if p = q = 0.5.
(6)
Examples
1. Ellen bought a share of stock for $10, and it is believed that the stock price moves (day
by day) as a simple random walk with p = 0.55. What is the probability that Ellen’s
stock reaches the high value of $15 before the low value of $5?
SOLUTION
We want “the probability that the stock goes up by 5 before going down by 5.” This is
equivalent to starting the random walk at 0 with a = 5 and b = 5, and computing p(a).
p(a) =
1 − (
q
p
)
b
1 − (
q
p
)
a+b
=
1 − (0.82)
5
1 − (0.82)
10
= 0.73
2. What is the probability that Ellen will becom e infinitely rich?
SOLUTION
Here we keep i = 10 in the Gambler’s ruin problem and let N → ∞ in the formula for
P
10
as in (4);
lim
N→∞
P
10
= 1 − (q/p)
10
= 1 − (.82)
10
= 0.86.
1.4 Markov chain approach
When we restrict the random walk to remain within the set of states {0, 1, . . . , N}, {R
n
} yields
a Markov chain (MC) on the state space S = {0, 1, . . . , N}. The transition probabilities are
given by P (R
n+1
= i + 1|R
n
= i) = p
i,i+i
= p, P (R
n+1
= i − 1|R
n
= i) = p
i,i−i
= q, 0 < i < N,
and both 0 and N are absorbing states, p
00
= p
NN
= 1.
1
For example, when N = 4 the transition matrix is given by
P =
1 0 0 0 0
q 0 p 0 0
0 q 0 p 0
0 0 q 0 p
0 0 0 0 1
.
Thus the gambler’s ruin problem can be viewed as a special case of a first passage time
problem: Compute the probability that a Markov chain, initially in state i, hits state j
1
before
state j
2
.
1
There are three communication classes: C
1
= {0}, C
2
= {1, . . . , N − 1}, C
3
= {N }. C
1
and C
3
are recurrent
whereas C
2
is transient.
4
