26 1. Random Walk and Discrete Heat Equation

terms for which the eigenvalue has maximal absolute value. These

two terms give

2

N

cosn

π

N

sin

πx

N

sin

πy

N

+

(−1)n

sin

xπ(N − 1)

N

sin

yπ(N − 1)

N

.

One can check that

sin

xπ(N − 1)

N

=

(−1)x+1

sin

πx

N

,

and, hence, if x, y ∈ {1,...,N − 1}, as n → ∞, then

P{Sn∧TA = y | S0 = x}

∼

2

N

cosn

π

N

[1 +

(−1)n+x+y]

sin

πx

N

sin

πy

N

.

For large n, conditioned such that the walker has not left {1,...,N −

1}, the probability that the walker is at y is about c sin(πy/N) as-

suming that the “parity” is correct (n + x + y is even). Other than

the parity, there is no dependence on the starting point x for the lim-

iting distribution. Note that the walker is more likely to be at points

toward the “middle” of the interval.

The above example illustrates a technique for finding solutions of

the form (1.15) called separation of variables. The same idea works for

all d although it may not always be possible to give nice expressions

for the eigenvalues and eigenvectors. For finite A this is essentially

the same as computing powers of a matrix by diagonalization. We

summarize here.

Theorem 1.7. If A is a finite subset of

Zd

with N elements, then

we can find N linearly independent functions φ1,...,φN that satisfy

(1.16) with real eigenvalues λ1,...,λN . The solution to (1.12)–(1.14)

is given by

pn(x) =

N

j=1

cj λj

n

φj(x),

where cj are chosen so that

f(x) =

N

j=1

cj φj(x).