1.2. Boundary value problems 19

The operator L is often called the (discrete) Laplacian. We let Sn be

a simple random walk in Zd. Then we can write

LF (x) = E[F (S1) − F (S0) | S0 = x].

We say that F is (discrete) harmonic at x if LF (x) = 0; this is an

example of a mean-value property. The corresponding boundary value

problem we will state is sometimes called the Dirichlet problem for

harmonic functions.

♦

The term linear operator is often used for a linear function whose

domain is a space of functions. In our case, the domain is the space of functions

on the finite set A which is isomorphic to

RK

where K = #(A). In this case a

linear operator is the same as a linear transformation from linear algebra. We

can think of Q and L as K × K matrices. We can write Q = [Q(x, y)]x,y∈A

where Q(x, y) = 1/(2d) if |x − y| = 1 and otherwise Q(x, y) = 0. Define

Qn(x, y) by

Qn

= [Qn(x, y)]. Then Qn(x, y) is the probability that the

random walk starts at x, is at site y at time n, and and has not left the set A

by time n.

Dirichlet problem for harmonic functions. Given a set A ⊂ Zd

and a function F : ∂A → R find an extension of F to A such that F

is harmonic in A, i.e.,

(1.9) LF (x) = 0 for all x ∈ A.

For the case d = 1 and A = {1,...,N − 1}, we were able to guess

the solution and then verify that it is correct. In higher dimensions,

it is not so obvious how to give a formula for the solution. We will

show that the last proof for d = 1 generalizes in a natural way to

d 1. We let TA = min{n ≥ 0 : Sn ∈ A}.

Theorem 1.5. If A ⊂

Zd

is finite, then for every F : ∂A → R, there

is a unique extension of F to A that satisfies (1.9). It is given by

F0(x) = E[F (STA ) | S0 = x] =

y∈∂A

P{STA = y | S0 = x} F (y).