12 1. Random Walk and Discrete Heat Equation
What is the probability that we are at the origin after n steps
assuming S0 = 0? This is zero if n is odd. If n is even, let us give
a heuristic argument. The typical distance from the origin of Sn is
of order

n. In d dimensions the number of lattice points within

n grows like (

Hence, the probability that we choose
a particular point should decay like a constant times
The combinatorics for justifying this is a little more complicated
than in the one-dimensional case, so we will just wave our hands to
get the right behavior. In 2n steps, we expect that approximately
2n/d of them will be taken in each of the d possible directions (e.g.,
if d = 2, we expect about n horizontal and n vertical steps). In
order to be at the origin, we need to take an even number of steps
in each of the d-directions. The probability of this (Exercise 1.17) is
Given that each of these numbers is even, the probability
that each individual component is at the origin is the probability
that a one-dimensional walk is at the origin at time 2n/d (or, more
precisely, an even integer very close to 2n/d). Using this idea we get
the asymptotics
P{S2n = 0}
, cd =
πd/2 2d−1
The particular value of cd will not be important to us, but the fact
that the exponent of n is d/2 is very important.
Consider the expected number of returns to the origin. If V is
the number of visits to the origin, then just as in the d = 1 case,
E[V ] =

P{S2n = 0}.
E[V ] =
1 q
where q = qd is the probability that the d-dimensional walk returns
to the origin. Since P{S2n = 0}
E[V ] =

P{S2n = 0} =
∞, d 3,
= ∞, d = 2
Theorem 1.2. Suppose Sn is simple random walk in
with S0 = 0.
If d = 1, 2, the random walk is recurrent, i.e., with probability one it
Previous Page Next Page