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