Chapter 1

Random Walk and

Discrete Heat Equation

1.1. Simple random walk

We consider one of the basic models for random walk, simple random

walk on the integer lattice

Zd.

At each time step, a random walker

makes a random move of length one in one of the lattice directions.

1.1.1. One dimension. We start by studying simple random walk

on the integers. At each time unit, a walker flips a fair coin and moves

one step to the right or one step to the left depending on whether the

coin comes up heads or tails. Let Sn denote the position of the walker

at time n. If we assume that the walker starts at x, we can write

Sn = x + X1 + · · · + Xn

where Xj equals ±1 and represents the change in position between

time j − 1 and time j. More precisely, the increments X1,X2,... are

independent random variables with P{Xj = 1} = P{Xj = −1} = 1/2.

Suppose the walker starts at the origin (x = 0). Natural questions

to ask are:

• On the average, how far is the walker from the starting

point?

1

http://dx.doi.org/10.1090/stml/055/01