2 1. Random Walk and Discrete Heat Equation

Sn

1 3 4 6 5 2 7 8

0

-1

-2

3

2

1

-3

n

Figure 1. One-dimensional random walk with x = 0

• What is the probability that at a particular time the walker

is at the origin?

• More generally, what is the probability distribution for the

position of the walker?

• Does the random walker keep returning to the origin or does

the walker eventually leave forever?

Probabilists use the notation E for expectation (also called ex-

pected value, mean, average value) defined for discrete random vari-

ables by

E[X] =

z

z P{X = z}.

The random walk satisfies E[Sn] = 0 since steps of +1 and −1 are

equally likely. To compute the average distance, one might try to