1.4. Expected time to escape 29

(−1)x1+···+xd . We call x even if par(x) = 1 and otherwise x is odd.

If n is a nonnegative integer, then

pn(x, y; A) = 0 if

(−1)npar(x

+ y) = −1.

If Qφ = λφ, then Q[parφ] = −λparφ.

Theorem 1.9. Suppose A is a finite connected subset of

Zd

with at

least two points. Then λ1 λ2, λN = −λ1 λN−1. The eigenfunc-

tion φ1 can be chosen so that φ1(x) 0 for all x ∈ A,

lim

n→∞

λ1

−n

pn(x, y; A) = [1 +

(−1)n

par(x + y)] φ1(x) φ1(y).

Example 1.10. One set in

Zd

for which we can compute the eigen-

functions and eigenvalues exactly is a d-dimensional rectangle,

A = {(x1,...,xd) ∈

Zd

: 1 ≤ xj ≤ Nj − 1}.

The eigenfunctions are indexed by

¯

k = (k1,...,kd) ∈ A,

φ¯(x1,...,xd)

k

= sin

k1πx1

N1

sin

k2πx2

N2

· · · sin

kdπxd

Nd

,

with eigenvalue

λ¯

k

=

1

d

cos

k1π

N1

+ · · · + cos

kdπ

Nd

.

1.4. Expected time to escape

1.4.1. One dimension. Let Sn denote a one-dimensional random

walk starting at x ∈ {0,...,N} and let T be the first time that the

walker reaches {0,N}. Here we study the expected time to reach 0

or N,

e(x) = E[T | S0 = x].

Clearly, e(0) = e(N) = 0. Now suppose x ∈ {1,...,N −1}. Then the

walker takes one step which goes to either x − 1 or x + 1. Using this

we get the relation

e(x) = 1 +

1

2

[e(x + 1) + e(x − 1)] .

Hence, e satisfies

(1.19) e(0) = e(N) = 0, Le(x) = −1, x = 1,...,N − 1.