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

distance

√

n grows like (

√

n)d.

Hence, the probability that we choose

a particular point should decay like a constant times

n−d/2.

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

2−(d−1).

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

nd/2

, cd =

dd/2

π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 ] =

∞

n=0

P{S2n = 0}.

Also,

E[V ] =

1

1 − q

,

where q = qd is the probability that the d-dimensional walk returns

to the origin. Since P{S2n = 0} ∼

c/nd/2,

E[V ] =

∞

n=0

P{S2n = 0} =

∞, d ≥ 3,

= ∞, d = 2

.

Theorem 1.2. Suppose Sn is simple random walk in

Zd

with S0 = 0.

If d = 1, 2, the random walk is recurrent, i.e., with probability one it