28 1. Random Walk and Discrete Heat Equation
where the supremum is over all functions f on A, and ·, · denotes
the inner product
f, g =
Proof. If φ is an eigenvector with eigenvalue λ1, then Qφ = λ1φ and
setting f = φ shows that the supremum is at least as large as λ1.
Conversely, there is an orthogonal basis of eigenfunctions φ1,...,φN
and we can write any f as
Qf, f = Q
φj,φj = λ1 f, f .
The reader should check that the computation above uses the orthog-
onality of the eigenfunctions and also the fact that φj,φj ≥ 0.
Using this variational formulation, we can see that the eigenfunc-
tion for λ1 can be chosen so that φ1(x) ≥ 0 for each x (since if φ1 took
on both positive and negative values, we would have Q|φ1|, |φ1|
φ1,φ1 ). The eigenfunction is unique, i.e., λ2 λ1, provided we
put an additional condition on A. We say that a subset A on Zd is
connected if any two points in A are connected by a nearest neighbor
path that stays entirely in A. Equivalently, A is connected if for each
x, y ∈ A there exists an n such that pn(x, y; A) 0. We leave it as
Exercise 1.23 to show that this implies that λ1 λ2.
Before stating the final theorem, we need to discuss some par-
ity (even/odd) issues. If x = (x1,...,xd) ∈
we let par(x) =