Random walk, gambler’s ruin and other good stuff.

Suppose 0 < p < 1 and let q = 1 − p. Let

X1 , X2 , . . . , Xn , . . .

be a sequence of mutually independent random variables with values in {−1, 1} such that

P (Xn = 1) = p, i = 1, 2, . . . , n, . . . .

It is not mathematically obvious that such a sequence of random variables exists; in fact, the sample space
must be uncountable. It is, however, intuitively clear that such a sequence, or something like it, exists.
For each n = 1, 2, . . . let
Xn
Sn = Xi .
i=1

The sequence Sn , n = 1, 2, . . . is an example of what is called a simple random walk and is extraordinarily
useful.

Consider a game in which you win or lose a dollar at the n-th play if Xn is 1 or −1, respectively. You
start playing with a fortune of f dollars with the goal of winning w dollars. You quit if either you are broke
or you have won w dollars. What is the probability you will win? Go broke? How long will you play? We
now proceed to answer all these questions.

Let
T
be the duration of play. That is, for each positive integer n, T = n if −f < Sj < w for all j < n and either
Sn = −f or Sn = w, and T = ∞ if you play forever because you never win and are never ruined. Here is an
important fact about T : the event {T < n} depends only on X1 , . . . , Xn−1 . This means, by definition, that
you can determine the value of T at a sample point if you know the values of X1 , . . . , Xn−1 at that sample
point, which, I hope, is clearly the case. This implies that the complementary event

(1) {T ≥ n} is independent of Xn , Xn+1 , . . . .

We now prove the basic

Theorem.

(2) P (T = ∞) = 0.

Proof. Let N = f + w − 1 and let λ = 1 − (pn + q n ). Let Ej be the event that not all of XjN +1 , . . . , X(j+1)N
are the same; note that
P (Ej ) = λ.
Now
{T ≥ (j + 1)N } ⊂ {T ≥ jN } ∩ Ej
so
P (T ≥ (j + 1)N ) ≤ P ({T ≥ jN } ∩ Ej ) = P (T ≥ jN ) P (Ej ) ≤ λ P (T ≥ jN )
where we have used (1) to obtain the equality. It follows that

P (T ≥ jN ) ≤ λj for j = 0, 1, 2, . . ..

Since {T = ∞} ⊂ {T ≥ jN } for all nonegative integers j and since limj→∞ λj = 0 we are done.

1
 Let us define
T
X
ST = Xi .
i=1

By virtue of (2) we find that

P (ST = f ) + P (ST = w) = 1.

Wald’s identities.

(3) E(ST ) = (p − q) E(T ).

(4) Var(ST ) = E(T ) provided p = q.

Proof. Using (1) we obtain

X∞
E(ST ) = E( Xi 1{T ≥i} )
i=1
∞
X
= E(Xi 1{T ≥i} )
i=1
X∞
= E(Xi ) E(1{T ≥i} )
i=1
X∞
= (p − q) P (T ≥ i)
i=1
= (p − q) E(T ),
proving (3). To prove (4), we assume that p = q and use (3) and (1) to calculate

Var(ST ) = E(ST2 )
X∞ ∞
X
= E( Xi 1{T ≥i} Xj 1{T ≥j} )
i=1 j=1
∞ X
X ∞
= E(Xi 1{T ≥i} Xj 1{T ≥j} )
i=1 j=1
X∞
= E(Xi2 12{T ≥i} )
i=1
∞
X
= E( 1{T ≥i} )
i=1
= E(T ),

where we have used that fact that

E(Xi 1{T ≥i} Xj 1{T ≥j} ) = 0 if i 6= j;

indeed, if i < j,
E(Xi 1{T ≥i} Xj 1{T ≥j} ) = E(Xi 1{T ≥i} 1{T ≥j} ) E(Xj ) = 0.

Let
pruin = P (ST = −f ) and pwin = P (ST = w).

2
All questions answered in case p = q. It follows directly from (3) that
−f pruin + w pwin = E(ST ) = 0
and (2) implies
pruin + pwin = 1.
Consequently,
w f
pruin = and pwin = .
f +w f +w
This in turn implies that
E(T ) = Var(ST ) = E(ST2 ) = f 2 pruin + w2 pwin = f w.

All questions answered in case p 6= q. We now need to vary f and w. For each integer n greater than
−f and less than w let
gn
be the probability of winning starting with an initial fortune of f + n dollars and trying to win w − n dollars.
We also
g−f = 0 and gw = 1.
The key fact is that
(5) gn = p gn+1 + q gn−1 , −f < n < w;
we leave it to the reader to prove this by conditioning on the outcome of the first play; make sure you
understand this as it’s the basis of everything that follows. Since p + q = 1 this gives
gn+1 − gn = ρ (gn − gn−1 ) −f < n < w
which implies that
gn+1 − gn = ρf +n g−f +1 , −f ≤ n < w,
where we have set
q
6= 1.
ρ=
p
Using the formula for summing a geometric progression we find that
1 − ρf +n
gn = g−f +1 , −f ≤ n ≤ w.
1−ρ
Since gw = 1 we find that
1−ρ
g−f +1 =
1 − ρf +w
so that
1 − ρ 1 − ρf +n 1 − ρf +n
gn = = , −f ≤ n ≤ w.
1 − ρf +w 1 − ρ 1 − ρf +w
Thus
1 − ρf 1 − ρf f 1−ρ
w
pwin = g0 = and pruin = 1 − pwin = 1 − = ρ .
1 − ρf +w 1 − ρf +w 1 − ρf +w
f w
Using L’Hôpital’s rule we note that these converge as ρ → 1 to f +w and f +w , respectively, which is nice.
This immediately gives
E(ST ) = −f pruin + wpwin .
From (3) we infer that
1
E(T ) = (−f pruin + wpwin ).
p−q