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
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
Previous Page Next Page