38 1. Random Walk and Discrete Heat Equation

(Although (1.29) gives this only for |x| = 1, we can apply the estimate

O(|x|) times to get this estimate.) By letting R → ∞ we see that

F (x) = F (0). Since this is true for every x, F must be constant.

1.5.1. Exterior Dirichlet problem. Consider the following prob-

lem. Suppose A is a cofinite subset of

Zd,

i.e., a subset such that

Zd

\ A is finite. Suppose F :

Zd

\ A → R is given. Find all bounded

functions on

Zd

that are harmonic on A and take on the boundary

value F on

Zd

\ A. If A =

Zd,

then this was answered at the end

of the last section; the only possible functions are constants. For the

remainder of this section we assume that A is nontrivial, i.e.,

Zd

\ A

is nonempty.

For d = 1, 2, there is, in fact, only a single solution. Suppose

F is such a function with L = sup |F (x)| ∞. Let Sn be a simple

random walk starting at x ∈ Zd, and let T = TA be the first time n

with Sn ∈ A. If d ≤ 2, we know that the random walk is recurrent

and hence T ∞ with probability one. As done before, we can see

that Mn = F (Sn∧T ) is a martingale and hence

F (x) = M0 = E[Mn] = E[F (ST ) 1{T ≤ n}] + E [F (Sn) 1{T n}] .

The monotone convergence theorem tells us that

lim

n→∞

E[F (ST ) 1{T ≤ n}] = E[F (ST )].

Also,

lim

n→∞

|E [F (Sn) 1{T n}]| ≤ lim

n→∞

L P{T n} = 0.

Therefore,

F (x) = E[F (ST ) | S0 = x],

which is exactly the same solution as we had for bounded A.

If d ≥ 3, there is more than one solution. In fact,

f(x) = P{TA = ∞ | S0 = x},

is a bounded function that is harmonic in A and equals zero on

Zd

\

A. The next theorem shows that this is essentially the only new

function that we get. We can interpret the theorem as saying that

the boundary value determines the function if we include ∞ as a

boundary point.