20 1. Random Walk and Discrete Heat Equation

It is not diﬃcult to verify that F0, as defined above, is a solution

to the Dirichlet problem. The problem is to show that it is unique.

Suppose F is harmonic on A, S0 = x ∈ A, and let

Mn = F (Sn∧TA ).

Then (1.9) can be rewritten as

(1.10) E[Mn+1 | S0,...,Sn] = F (Sn∧TA ) = Mn.

A process that satisfies E[Mn+1 | S0,...,Sn] = Mn is called a martin-

gale (with respect to the random walk). It is easy to see that F (Sn∧TA )

being a martingale is essentially equivalent to F being harmonic on

A. It is easy to check that martingales satisfy E[Mn] = E[M0], and

hence if S0 = x, then

y∈A

P{Sn∧TA = y} F (y) = E[Mn] = M0 = F (x).

An easy argument shows that with probability one TA ∞. We can

take limits and get

(1.11)

F (x) = lim

n→∞

y∈A

P{Sn∧TA = y} F (y) =

y∈∂A

P{STA = y} F (y).

♦

There is no problem interchanging the limit and the sum because it is a

finite sum. If A is infinite, one needs more assumptions to justify the exchange

of the limit and the sum.

Let us consider this from the perspective of linear algebra. Sup-

pose that A has N elements and ∂A has K elements. The solution

of the Dirichlet problem assigns to each function on ∂A (a vector in

RK ) a function on A (a vector in RN ). Hence the solution can be

considered as a linear function from RK to RN (the reader should

check that this is a linear transformation). Any linear transformation

is given by an N ×K matrix. Let us write the matrix for the solution

as

HA = [HA(x, y)]x∈A,y∈∂A.

Another way of stating (1.11) is to say that

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