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).
Previous Page Next Page