20 1. Random Walk and Discrete Heat Equation
It is not difficult 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} .
Previous Page Next Page