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].
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

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-
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
and each particular choice of 2n +1’s
and −1’s has probability
of occurring. Therefore,
P{S2n = 0} =
n! n!
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} =
n + j
(n + j)! (n j)!
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
Previous Page Next Page