46 1. Random Walk and Discrete Heat Equation

Exercise 1.22. Suppose Sn is a simple random walk in Zd and A ⊂

Zd is finite with N points. Let TA be the smallest n such that Sn ∈ A.

Show that

P{TA kN} ≤ 1 −

1

2d

k

.

Exercise 1.23. Finish the proof of Theorem 1.9 by doing the follow-

ing:

• Use connectedness of A to show that any nonzero eigen-

function φ with every component nonnegative must actually

have every component strictly positive.

• Give an example of a disconnected A such that λ1 has mul-

tiplicity greater than one.

• Given an example of a disconnected A such that λ1 has

multiplicity one. Does Theorem 1.9 hold in this case?

Exercise 1.24. Suppose A is a bounded subset of Zd. We call {x, y}

an edge of A if x, y ∈ A, |x − y| = 1 and at least one of x, y is in A.

If F : A → R is a function, we define its energy by

E(f) = [f(x) −

f(y)]2,

where the sum is over the edges of A. For any F : ∂A → R, define

E(F ) to be the infimum of E(f) where the infimum is over all f on A

that agree with F on ∂A. Show that if f agrees with F on ∂A, then

E(f) = E(F ) if and only if f is harmonic in A.

Exercise 1.25. Verify (1.31).

Exercise 1.26. We will construct a “tree” each of whose vertices has

three neighbors. We start by constructing T1 as follows: the vertices

of T1 are the “empty word”, denoted by o, and all finite sequences of

the letters a, b, i.e., “words” x1 · · · xn where x1,x2,...,xn ∈ {a, b}.

Both words of one letter are adjacent to o. We say that a word of

length n − 1 and of length n are adjacent if they have the exact same

letters, in order, in the first n − 1 positions. Note that each word of

positive length is adjacent to three words and the root is adjacent to

only two words. We construct another tree T2 similarly, calling the

root ˜ o and using the letters ˜ a,

˜.

b Finally, we make a tree T by taking