4Interesting problems
IA Probability
4.2 Random walk and gambler’s ruin
Here we’ll study random walks, using gambler’s ruin as an example.
Definition (Random walk). Let
X
1
, ··· , X
n
be iid random variables such
that
X
n
= +1 with probability
p
, and
−
1 with probability 1
− p
. Let
S
n
=
S
0
+ X
1
+ ··· + X
n
. Then (S
0
, S
1
, ··· , S
n
) is a 1-dimensional random walk.
If p = q =
1
2
, we say it is a symmetric random walk.
Example. A gambler starts with $
z
, with
z < a
, and plays a game in which he
wins $1 or loses $1 at each turn with probabilities
p
and
q
respectively. What
are
p
z
= P(random walk hits a before 0 | starts at z),
and
q
z
= P(random walk hits 0 before a | starts at z)?
He either wins his first game, with probability
p
, or loses with probability
q
. So
p
z
= qp
z−1
+ pp
z+1
,
for 0 < z < a, and p
0
= 0, p
a
= 1.
Try p
z
= t
z
. Then
pt
2
− t + q = (pt − q)(t − 1) = 0,
noting that p = 1 − q. If p = q, then
p
z
= A1
z
+ B
q
p
z
.
Since p
0
= 0, we get A = −B. Since p
a
= 1, we obtain
p
z
=
1 − (q/p)
z
1 − (q/p)
a
.
If p = q, then p
z
= A + Bz = z/a.
Similarly, (or perform the substitutions p 7→ q, q 7→ p and z 7→ a − z)
q
z
=
(q/p)
a
− (q/p)
z
(q/p)
a
− 1
if p = q, and
q
z
=
a − z
a
if p = q. Since p
z
+ q
z
= 1, we know that the game will eventually end.
What if a → ∞? What is the probability of going bankrupt?
P(path hits 0 ever) = P
∞
[
a=z+1
[path hits 0 before a]
!
= lim
a→∞
P(path hits 0 before a)
= lim
a→∞
q
z
=
(
(q/p)
z
p > q
1 p ≤ q.
So if the odds are against you (i.e. the probability of losing is greater than the
probability of winning), then no matter how small the difference is, you are
bound to going bankrupt eventually.
Duration of the game
Let
D
z
= expected time until the random walk hits 0 or
a
, starting from
z
. We
first show that this is bounded. We know that there is one simple way to hit 0
or
a
: get +1 or
−
1 for
a
times in a row. This happens with probability
p
a
+
q
a
,
and takes
a
steps. So even if this were the only way to hit 0 or
a
, the expected
duration would be
a
p
a
+q
a
. So we must have
D
z
≤
a
p
a
+ q
a
This is a very crude bound, but it is sufficient to show that it is bounded, and
we can meaningfully apply formulas to this finite quantity.
We have
D
z
= E[duration]
= E[E[duration | X
1
]]
= pE[duration | X
1
= 1] + qE[duration | X
1
= −1]
= p(1 + D
z+1
) + q(1 + D
z−1
)
So
D
z
= 1 + pD
z+1
+ qD
z−1
,
subject to D
0
= D
a
= 0.
We first find a particular solution by trying D
z
= Cz. Then
Cz = 1 + pC(z + 1) + qC(z − 1).
So
C =
1
q − p
,
for p = q. Then we find the complementary solution. Try D
z
= t
z
.
pt
2
− t + q = 0,
which has roots 1 and q/p. So the general solution is
D
z
= A + B
q
p
z
+
z
q − p
.
Putting in the boundary conditions,
D
z
=
z
q − p
−
a
q − p
·
1 − (q/p)
z
1 − (q/p)
a
.
If p = q, then to find the particular solution, we have to try
D
z
= Cz
2
.
Then we find C = −1. So
D
z
= −z
2
+ A + Bz.
Then the boundary conditions give
D
z
= z(a − z).
Using generating functions
We can use generating functions to solve the problem as well.
Let U
z,n
= P(random walk absorbed at 0 at n | start in z).
We have the following conditions:
U
0,0
= 1;
U
z,0
= 0 for 0
< z ≤ a
;
U
0,n
= U
a,n
= 0 for n > 0.
We define a pgf-like function.
U
z
(s) =
∞
X
n=0
U
z,n
s
n
.
We know that
U
z,n+1
= pU
z+1,n
+ qU
z−1,n
.
Multiply by s
n+1
and sum on n = 0, 1, ···. Then
U
z
(s) = psU
z+1
(s) + qsU
z−1
(s).
We try U
z
(s) = [λ(s)]
z
. Then
λ(s) = psλ(s)
2
+ qs.
Then
λ
1
(s), λ
2
(s) =
1 ±
p
1 − 4pqs
2
2ps
.
So
U
z
(s) = A(s)λ
1
(s)
z
+ B(s)λ
2
(s)
z
.
Since U
0
(s) = 1 and U
a
(s) = 0, we know that
A(s) + B(s) = 1
and
A(s)λ
1
(s)
a
+ B(s)λ
2
(s)
a
= 0.
Then we find that
U
z
(s) =
λ
1
(s)
a
λ
2
(s)
z
− λ
2
(s)
a
λ
1
(s)
z
λ
1
(s)
a
− λ
2
(s)
a
.
Since λ
1
(s)λ
2
(s) =
q
p
, we can “simplify” this to obtain
U
z
(s) =
q
p
z
·
λ
1
(s)
a−z
− λ
2
(s)
a−z
λ
1
(s)
a
− λ
2
(s)
a
.
We see that
U
z
(1) =
q
z
. We can apply the same method to find the generating
function for absorption at
a
, say
V
z
(
s
). Then the generating function for the
duration is U
z
+ V
z
. Hence the expected duration is D
z
= U
′
z
(1) + V
′
z
(1).