30 1. Random Walk and Discrete Heat Equation
A simple calculation shows that if f(x) = x2, then Lf(x) = 1 for all
x. Also, the linear function g(x) = x is harmonic, Lg 0. Using this
we can see that one solution to (1.19) is
e(x) = x (N x).
In fact, as we will now show, it is the unique solution. Assume that
e1 is another solution. Then for x = 1,...,N 1,
L(e e1)(x) = Le(x) Le1(x) = −1 (−1) = 0,
i.e., e e1 is harmonic on {1,...,N 1}. Since this function also
vanishes at 0 and N we know that e e1 = 0.
Suppose N = 2m is even. Then we get
e(m) = N
2/4
=
m2.
In other words, the expected time for a random walker starting at m
(or anywhere else, in fact) to go distance m is exactly
m2.
Suppose the random walker starts at x = 1. Then the expected
time to leave the interval is N 1. While this is an expected value,
it is not necessarily a “typical” value. Most of the time the random
walker will leave quickly. However, the gambler’s ruin estimate tells
us that there is a probability of 1/m that the random walker will
reach m before leaving the interval. If that happens, then the walker
will still have on the order of N
2
steps before leaving.
One other interesting fact concerns the time until a walker start-
ing at 1 reaches the origin. Let T0 be the first n such that Sn = 0.
If S0 = 1, we know that T0 with probability one. However, the
amount of time to reach 0 is at least as large as the amount of time
to reach 0 or N. Therefore, E[T0] N. Since this is true for every
N, we must have E[T0] = ∞. In other words, while it is guaranteed
that a random walker will return to the origin the expected amount
of time until it happens is infinite!
1.4.2. Several dimensions. Let A be a finite subset of Zd, Sn a
simple random walker starting at x A, and TA the first time that
the walker is not in A. Let
eA(x) = E[TA | S0 = x].
Previous Page Next Page