Lecture 5: Random walks - advanced methods 1 of 12

Course: Introduction to Stochastic Processes

Term: Fall 2019
Instructor: Gordan Žitković

Lecture 5
Random walks - advanced methods

5.1 Stopping times

Our last application of generating functions dealt with sums evaluated be-
tween 0 and some random time N. An especially interesting case occurs
when the value of N depends directly on the evolution of the underlying
stochastic process. Even more important is the case where time’s arrow is
taken into account. If you think of N as the time you stop adding new terms
to the sum, it is usually the case that you are not allowed (able) to see the
values of the terms you would get if you continued adding. Think of an
investor in the stock market. Her decision to stop and sell her stocks can
depend only on the information available up to the moment of the decision.
Otherwise, she would sell at the absolute maximum and buy at the abso-
lute minimum, making tons of money in the process. Of course, this is not
possible unless you are clairvoyant, so the mere mortals have to restrict their
choices to so-called stopping times.

Definition 5.1.1. Let { Xn }n∈N0 be a stochastic process. A random

variable T taking values in N0 ∪ {+∞} is said to be a stopping time
with respect to { Xn }n∈N0 if for each n ∈ N0 there exists a function
G n : Rn+1 → {0, 1} such that

1{T =n} = G n ( X0 , X1 , . . . , Xn ), for all n ∈ N0 .

The functions G n are called the decision functions, and should be thought
of as a black box which takes the values of the process { Xn }n∈N0 observed
up to the present point and outputs either 0 or 1. The value 0 means keep
going and 1 means stop. The whole point is that the decision has to based
only on the available observations and not on the future ones.

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 2 of 12

Example 5.1.2.

1. The simplest examples of stopping times are (non-random) deter-

ministic times. Just set T = 5 (or T = 723 or T = n0 for any
n0 ∈ N0 ∪ {+∞}), no matter what the state of the world ω ∈ Ω is.
The family of decision rules is easy to construct:
(
n 1, n = n0 ,
G ( x0 , x1 , . . . , x n ) = .
0, n 6= n0 .

Decision functions G n do not depend on the values of

X0 , X1 , . . . , Xn at all. A gambler who stops gambling after 20 games,
no matter of what the winnings or losses are uses such a rule.
2. Probably the most well-known examples of stopping times are
(first) hitting times. They can be defined for general stochastic pro-
cesses, but we will stick to simple random walks for the purposes
of this example. So, let Xn = ∑nk=0 ξ k be a simple random walk, and
let Tl be the first time X hits the level l ∈ Ne More precisely, we
use the following slightly non-intuitive but mathematically correct
definition
Tl = min{n ∈ N0 : Xn = l }.
The set {n ∈ N0 : Xn = l } is the collection of all time-points at
which X visits the level l. The earliest one - the minimum of that set
- is the first hitting time of l. In states of the world ω ∈ Ω in which
the level l just never gets reached, i.e., when {n ∈ N0 : Xn = l }
is an empty set, we set Tl (ω ) = +∞. In order to show that Tl is
indeed a stopping time, we need to construct the decision functions
G n , n ∈ N0 . Let us start with n = 0. We would have Tl = 0 in the
(impossible) case X0 = l, so we always have G0 ( X0 ) = 0. How
about n ∈ N. For the value of Tl to be equal to exactly n, two
things must happen:
a) Xn = l (the level l must actually be hit at time n), and
b) Xn−1 6= l, Xn−2 6= l, . . . , X1 6= l, X0 6= l (the level l has not been
hit before).
Therefore,
(
n 1, x0 6= l, x1 6= l, . . . , xn−1 6= l, xn = l
G ( x0 , x1 , . . . , x n ) =
0, otherwise.

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 3 of 12

The hitting time T2 of the level l = 2 for a particular trajectory of a

symmetric simple random walk is depicted below:

5 10 15 20 25 30
-2 T2 TM
-4

-6 .

3. How about something that is not a stopping time? Let T ∈ N

be an arbitrary time-horizon and let TM be the last time during
0, . . . , T that the random walk visits its maximum during 0, . . . , T
(see picture above, where T = 30). If you bought a stock at time
n = 0, had to sell it some time before or at T and had the ability
to predict the future, this is one of the points you would choose to
sell it at. Of course, it is impossible in general to decide whether
TM = n, for some n ∈ 0, . . . , T − 1 without the knowledge of the
values of the random walk after n. More precisely, let us sketch the
proof of the fact that TM is not a stopping time. Suppose, to the
contrary, that it is, and let G n be the family of decision functions.
Consider the following two trajectories: (0, 1, 2, 3, . . . , T − 1, T ) and
(0, 1, 2, 3, . . . , T − 1, T − 2). They differ only in the direction of the
last step. They also differ in the fact that TM = T for the first one
and TM = T − 1 for the second one. On the other hand, by the
definition of the decision functions, we have

1{TM =T −1} = G T −1 ( X0 , . . . , XT −1 ).

The right-hand side is equal for both trajectories, while the left-
hand side equals to 0 for the first one and 1 for the second one. A
contradiction.

5.2 Wald’s identity II and Gambler’s Ruin

Having defined the notion of a stopping time, let us try to compute some-
thing about it. The random variables {ξ n }n∈N in the statement of the theorem
below are only assumed to be independent of each other and identically dis-
tributed. To make things simpler, you can think of {ξ n }n∈N as increments of

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 4 of 12

a simple random walk. Before we state the main result, here is an extremely
useful identity:

Proposition 5.2.1 (Tail formula for the expectation). Let N be an N0 -

valued random variable. Then
∞
E[ N ] = ∑ P[ N ≥ k ].
k =1

Proof. Clearly, P[ N ≥ k] = ∑ j≥k P[ N = j], so (note what happens to the

indices when we switch the sums)
∞ ∞ ∞ j ∞
∑ P[ N ≥ k] = ∑ ∑ P[ N = j] = ∑ ∑ P[n = j] = ∑ jP[ N = j] = E[ N ].
k =1 k =1 j ≥ k j =1 k =1 j =1

Theorem 5.2.2 (Wald’s Identity II). Let {ξ n }n∈N be a sequence of inde-

pendent, identically distributed random variables with E[|ξ 1 |] < ∞. Set
n
Xn = ∑ ξk, n ∈ N0 .
k =1

If T is an { Xn }n∈N0 -stopping time such that E[ T ] < ∞, then

E[ X T ] = E[ ξ 1 ]E[ T ].

Proof. Here is another way of writing the sum ∑kT=1 ξ k :

T ∞
∑ ξ k = ∑ ξ k 1{k≤ T } .
k =1 k =1

The idea behind it is simple: add all the values of ξ k for k ≤ T and keep
adding zeros (since ξ k 1{k≤T } = 0 for k > T) after that. Taking expectation of
both sides and switching E and ∑ (this can be justified, but the argument is
technical and we omit it here) yields:
T ∞
E[ ∑ ξ k ] = ∑ E[ 1 { k ≤ T } ξ k ]. (5.2.1)
k =1 k =1

Let us examine the term E[ξ k 1{k≤T } ] in some detail. We first note that

k −1
1 { k ≤ T } = 1 − 1 { k > T } = 1 − 1 { k −1≥ T } = 1 − ∑ 1{ T = j} .
j =0

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 5 of 12

Therefore,
k −1
E[ ξ k 1 { k ≤ T } ] = E[ ξ k ] − ∑ E[ ξ k 1 { T = j } ].
j =0

By the assumption that T is a stopping time, the indicator 1{T = j} can be

represented as 1{T = j} = G j ( X0 , . . . , X j ), and, because each Xi is just a sum of
the increments, we can actually write 1{T = j} as a function of ξ 1 , . . . , ξ j only
- say 1{T = j} = H j (ξ 1 , . . . , ξ j ). By the independence of (ξ 1 , . . . , ξ j ) from ξ k
(because j < k) we have

E[ξ k 1{T = j} ] = E[ξ k H j (ξ 1 , . . . , ξ j )] = E[ξ k ]E[ H j (ξ 1 , . . . , ξ j )]

= E[ ξ k ]E[ 1 { T = j } ] = E[ ξ k ]P[ T = j ].

Therefore,
k −1
E[ ξ k 1 { k ≤ T } ] = E[ ξ k ] − ∑ E[ ξ k ]P[ T = j ] = E[ ξ k ]P[ T ≥ k ]
j =0

= E[ ξ 1 ]P[ T ≥ k ],
where the last equality follows from the fact that all ξ k have the same distri-
bution.
Going back to (5.2.1), we get
T ∞
E[ X T ] = E[ ∑ ξ k ] = ∑ E[ ξ 1 ]P[ T ≥ k ]
k =1 k =1
∞
= E[ ξ 1 ] ∑ P[ T ≥ k ] = E[ ξ 1 ]E[ T ],
k =1

where we use Proposition 5.2.1 for the last equality.

Example 5.2.3 (Gambler’s ruin problem). . A gambler starts with $x

dollars and repeatedly plays a game in which he wins a dollar with
probability 21 and loses a dollar with probability 12 . He decides to stop
when one of the following two things happens:
1. he goes bankrupt, i.e., his wealth hits 0, or
2. he makes enough money, i.e., his wealth reaches some level a > x.
The classical “Gambler’s ruin” (dating at least to 1600s) problem asks
the following question: what is the probability that the gambler will
make a dollars before he goes bankrupt?
Gambler’s wealth {Wn }n∈N is modeled by a simple random walk
starting from x, whose increments ξ k = Wk − Wk−1 are coin-tosses.

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 6 of 12

Then Wn = x + Xn , where Xn = ∑nk=0 ξ k , n ∈ N0 . Let T be the time

the gambler stops. We can represent T in two different (but equiv-
alent) ways. On the one hand, we can think of T as the smaller of
the two hitting times T− x and Ta− x of the levels − x and a − x for the
random walk { Xn }n∈N0 (remember that Wn = x + Xn , so these two
correspond to the hitting times for the process {Wn }n∈N0 of the levels
0 and a). On the other hand, we can think of T as the first hitting time
of the two-element set {− x, a − x } for the process { Xn }n∈N0 . In either
case, it is quite clear that T is a stopping time (can you write down
the decision functions?). When we talked about the maximum of the
simple symmetric random walk, we proved that it hits any value if
given enough time. Therefore, the probability that that the gambler’s
wealth will remain strictly between 0 and a forever is zero and so,
P[ T < ∞] = 1.
What can we say about the random variable XT - the gambler’s wealth
(minus x) at the random time T? Clearly, it is either equal to − x or to
a − x, and the probabilities p0 and p a with which it takes these values
are exactly what we are after in this problem. We know that, since
there are no other values XT can take, we must have p0 + p a = 1.
Second Wald’s identity gives us the second equation for p0 and p a :

E[ XT ] = E[ξ 1 ]E[ T ] = 0 · E[ T ] = 0,

so
0 = E[ XT ] = p0 (− x ) + p a ( a − x ).
These two linear equations with two unknowns yield
a−x x
p0 = , pa = .
a a
It is remarkable that the two probabilities are proportional to the
amounts of money the gambler needs to make (lose) in the two out-
comes. The situation is different when p 6= 21 .

5.3 The distribution of the first hitting time of a simple

symmetric random walk
Let { Xn }n∈N0 be a simple random walk, with the probability p of stepping
up. Let T1 = min{n ∈ N0 : Xn = 1} be the first hitting time of level l = 1,
and let { pn }n∈N0 be its pmf, i.e., pn = P[ T1 = n], n ∈ N0 . The goal of this
section is to use the powerful generating-function methods to find { pn }n∈N0 .

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 7 of 12

A recursive formula. We start with a simple observation that you cannot

get from 0 to 1 for the first time in an even number of steps. Therefore,
p2n = 0, n ∈ N0 . Also, p1 = p - you simply have to go up on the first step.
What about n > 1? In order to go from 0 to 1 in n > 1 steps (and not
before!) the first step needs to be down and then you need to climb up from
−1 to 1 in n − 1 steps. Climbing from −1 to 1 is exactly the same as climbing
from −1 to 0 and then climbing from 0 to 1. If it took j steps to go from
−1 to 0 it will have to take n − 1 − j steps to go from 1 to 2, where j can be
anything from 1 to n − 2, in order to finish the job in exactly n − 1 steps. So,
using formulas, we have

n −2 h
P[ T1 = n] = q ∑ P “exactly j steps to first hit 0 from −1”
j =1 (5.3.1)
i
and “exactly n − 1 − j steps to first hit 1 from 0” .

But there is nothing special about 0 as a starting point. Taking j steps

from −1 to 0 is exactly the same as taking j steps from 0 to 1, so

P[“exactly j steps to first hit 0 from −1”] = P[ T1 = j] = p j .

By the same token,

P[“exactly n-1-j steps to first hit 1 from 0”] = P[ T1 = n − 1 − j]

= p n −1− j .

Finally, I claim that the two events are independent of each other. Indeed,
once we have reached 0, the future increments of the random walk behave
exactly the same as the increments of a fresh random walk starting from zero
- they are independent of everything that happened in the past. Equivalently,
a knowledge of everything that happened until the moment the random walk
hit 0 for the first time does not change our perception (and estimation) of
what is going to happen later (in this case the likelihood of hitting 1 in exactly
n − 1 − j steps). This property is called the regeneration property or the strong
Lévy property of random walks. More precisely (but still not entirely precise),
we can make the following claim:

Let { Xn }n∈N0 be a simple random walk and let T be any N0 -

valued stopping time. Define the process {Yn }n∈N0 by Yn =
XT +n − XT . Then {Yn }n∈N0 is also a simple random walk, and
it is independent of X up to T.

In order to check your understanding, try to convince yourself that the re-
quirement that T be a stopping time is necessary - find an example of a
random time T which is not a stopping time where the statement above fails.

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 8 of 12

We can go back to the distribution of the hitting time T1 , and use our
newly-found independence together with (5.3.1) to obtain the following re-
cursion
n −2
pn = q ∑ p j pn− j−1 , n > 1, p0 = 0, p1 = p. (5.3.2)
j =1

Generating-function approach This is where generating functions step in.

We will use (5.3.2) to derive an equation for the generating function P(s) =
∑∞ k
k =0 pk s . The sum on the right-hand side of (5.3.2) looks a little bit like a
convolution, so let us compare it to the following expansion of the square
P ( s )2 :
∞ k
P ( s )2 = ∑ ( ∑ pi p k −i ) s k .
k =0 i =0

The inner sum ∑ik=0

pi pk−i needs to be split into several parts to get an ex-
pression which matches (5.3.2):

k k −1 (k+1)−2
p0 p k + ∑ p i p k −i + p k p0 =
∑ pi pk−i = |{z} ∑ pi p(k+1)−i−1
i =0 i =1 i =1
|{z}
0 0
−1
=q pk+1 , for k ≥ 2.

Therefore, since the coefficients of P(s)2 start at s2 , we have

∞ ∞
qsP(s)2 = qs ∑ q−1 pk+1 sk = ∑ pk+1 sk+1 = P(s) − ps,
k =2 k =2

which is nothing but a quadratic equation for P.

Remark 5.3.1. Here is another - shorter, but less rigorous - way of deriving
the same equation for P. The first hitting time T1 can be written as follows:
(
1, X1 = 1,
T1 = 0 00
1 + T1 + T1 , X1 = −1,

where T10 is the time it takes to hit 0 from −1 and T100 is the time it takes to hit
1 from 0. The notation T10 and T100 is suggestive of the fact that T10 and T100 have
the same distribution as T1 . Moreover, they are independent of each other,
as argued above. Using the expression PX (s) = E[s X ] and the law of total
probability with conditioning on the first step, we get

P(s) = E[s T1 ] = E[s T1 | X1 = 1] × P[ X1 = 1] + E[s T2 | X1 = −1] × P[ X1 = −1]

0 00 0 00
= pE[s1 | X1 = 1] + qE[s1+T1 +T1 ] = ps + qE[s1+T1 +T1 ]
0 00
= ps + qsE[s T1 ] × E[S T1 ] = ps + qsP(s)2 .

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 9 of 12

Now that we have the following equation for P:

P(s) = ps + qsP(s)2 , (5.3.3)

the first task is to solve it. It is a quadratic equation in P(s), so so it admits

two solutions (for each s):
p
1 ± 1 − 4pqs2
P(s) = .
2qs

One of the two solutions is always greater than 1 in absolute value, so it

cannot correspond to a value of a generating function. Therefore,
p
1 − 1 − 4pqs2 1
P(s) = , for |s| ≤ √ .
2qs 2 pq

It remains to extract the information about { pn }n∈N0 from P. We will not de-
rive expressions for all pn (but see the last problem in the Problems section),
because we do not need to. We can get very useful information from P itself.

Do we actually hit 1 sooner or later? What happens if we try to evaluate

P(1)? We should get 1, right? In fact, what we get is the following:
(
1, p ≥ 12
p
1 − 1 − 4pq 1 − | p − q|
P (1) = = = p 1
2q 2q q, p < 2

Clearly, P(1) < 1 when p < q. The explanation is simple - the random walk
may fail to hit the level 1 at all, if p < q. In that case P(1) = ∑∞
k =0 pk = P[ T1 <
∞] < 1, or, equivalently, P[ T1 = +∞] > 0. It is remarkable that if p = 21 ,
the random walk will always hit 1 sooner or later, but this does not need to
happen if p < 21 . What we have here is an example of a phenomenon known
as criticality: many physical systems exhibit qualitatively different behavior
depending on whether the value of certain parameter p lies above or below
certain critical value p = pc .

Expected time until we hit 1? Another question that generating functions

can help answer is the following one: how long, on average, do we need to
wait before 1 is hit? When p < 21 , P[ T1 = +∞] > 0, so we can immediately
conclude that E[ T1 ] = +∞, by definition. The case p ≥ 12 is more interesting.
Following the recipe from the lecture on generating functions, we compute
the derivative of P(s) and get
p
0 2p 1 − 1 − 4pqs2
P (s) = − .
2qs2
p
1 − 4pqs2

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 10 of 12

• When p = 12 , we get
√
 1 1 − 1 − s2 
lim P0 (s) = lim √ − = +∞,
s %1 s %1 1 − s2 s2

and conclude that E[ T1 ] = +∞.

• For p > 12 , the situation is less severe:

1
lim P0 (s) = .
s %1 p−q

We can summarize the situation in the following table

P[ T1 < ∞] E[ T1 ]
p
p< 1
2 q +∞

p= 1
2 1 +∞
1 1
p> 2 1 p−q

5.4 Problems
Problem 5.4.1. Either one of the following 4 random times is not a stopping
time for a simple random walk { Xn }n∈N0 , or they all are. Choose the one
which is not in the first case, or choose (e) if you think they all are.

(a) the first hitting time of the level 4,

(b) the first time n such that Xn − Xn−1 6= X1 ,
(c) the first time the walk hits the level 2 or the first time the walk sinks
below −5, whatever happens first,
(d) the second time the walk crosses the level 5 or the third time the walk
crosses the level −2, whatever happens last,
(e) none of the above.

Problem 5.4.2. Let T1 be the first hitting time of the level 1, for a simple
symmetric random walk { Xn }n∈N0 . Then

(a) P[ T1 < ∞] = 1 and E[ T1 ] < ∞,

(b) P[ T1 < ∞] < 1 and E[ T1 ] < ∞,
(c) P[ T1 < ∞] = 1 and E[ T1 ] = ∞,

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 11 of 12

(d) P[ T1 < ∞] < 1 and E[ T1 ] = ∞,

(e) none of the above.

Problem 5.4.3. The generating function PT−1 of the first hitting time T−1 of
the level −1 for the simple biased random walk with p = P[ X1 = 1] satisfies

(a) PT−1 (s) = ps + qsPT−1 (s)2 ,

(b) PT−1 (s) = qs + psPT−1 (s)2 ,

(c) PT−1 (s) = ps − qsPT−1 (s)2 ,

(d) PT−1 (s) = ps + qsPT−1 (s)−2 ,

(e) none of the above.

Problem 5.4.4. Let { Xn }n∈N0 be a simple biased random walk with p =

P[ X1 = 1], and Let Tl denote the first hitting time of the level l, and PTl
denote its generating function. Then

(a) PT2 (s) = ps + qsPT2 (s)4 ,

(b) PT2 (s) = ps2 + qsPT2 (s),

(c) PT2 (s) = PT1 (s),

(d) PT2 (s) = PT1 (s)2 ,

(e) none of the above.

Problem 5.4.5. If PTa denotes the generating function of the first hitting time
Ta of the level a for the simple symmetric random walk, then

(a) PT2 (s) = 12 sPT3 (s) + 12 sPT1 (s),

(b) PT2 (s) = 21 PT3 (s) + 21 PT1 (s),

(c) PT2 (s) = sPT3 (s) PT1 (s),

(d) PT2 (s) = 13 (s + PT3 (s) + 12 PT1 (s)),

(e) none of the above.

Last Updated: September 25, 2019

Lecture 5: Random walks - advanced methods 12 of 12

Problem 5.4.6. (*) The purpose of this problem is to derive explicit expres-
sions for the probabilities pn = P[ T1 = n], where T1 is the first hitting time of
the level 1 for a simple biased random walk { Xn }n∈N0 with p = P[ X1 = 1].
Our starting point is the expression
 q 
1
P(s) = 2qs 1 − 1 − 4pqs2

for the generating function P(s) = PT1 (s) derived in the notes.
√
1. Consider the function f ( x ) = 1 − x. Find an expression for the its n-th
derivative f (n) (0) at x = 0. Note: The following notation n!! = n × (n − 2) × (n −
4) × . . . , for the product of all positive integers up to n of the same parity as n, is going to
be useful.

2. Use the above to expand P(s) in a power-series expansion around s = 0

and write down the expressions for the coefficients pn , n ∈ N0 .

Last Updated: September 25, 2019