4 1. Random Walk and Discrete Heat Equation

♦

The sum rule for expectation and the fact that the cross terms E[Xj Xk]

vanish make it much easier to compute averages of the square of a random

variable than other powers. In many ways, this is just an analogy of the

Pythagorean theorem from geometry: the property E[XjXk] = 0, which fol-

lows from the fact that the random variables are independent and have mean

zero, is the analogue of perpendicularity or orthogonality of vectors.

Finding the probability that the walker is at the origin after n

steps is harder than computing E[Sn].

2

However, we can use our com-

putation to make a guess about the size of the probability. Since

E[Sn] 2 = n, the typical distance away from the origin is of order

√

n.

There are about

√

n integers whose distance is at most

√

n from the

starting point, so one might guess that the probability for being at

a particular one should decay like a constant times n−1/2. This is

indeed the case as we demonstrate by calculating the probability ex-

actly.

It is easy to see that after an odd number of steps the walker is

at an odd integer and after an even number of steps the walker is at

an even integer. Therefore, P{Sn = x} = 0 if n + x is odd. Let us

suppose the walker has taken an even number of steps, 2n. In order

for a walker to be back at the origin at time 2n, the walker must have

taken n “+1” steps and n “−1” steps. The number of ways to choose

which n steps are +1 is

(2n)

n

and each particular choice of 2n +1’s

and −1’s has probability

2−2n

of occurring. Therefore,

P{S2n = 0} =

2n

n

2−2n

=

(2n)!

n! n!

2−2n.

More generally, if the walker is to be at 2j, there must be (n + j)

steps of +1 and (n − j) steps of −1. The probabilities for the number

of +1 steps are given by the binomial distribution with parameters

2n and 1/2,

P{S2n = 2j} =

2n

n + j

2−2n

=

(2n)!

(n + j)! (n − j)!

2−2n.

While these formulas are exact, it is not obvious how to use them be-

cause they contain ratios of very large numbers. Trying to understand