18 1. Random Walk and Discrete Heat Equation

Considering the case F (0) = 0,F (N) = 1 gives P{ST = N | S0 =

x} = x/N and for more general boundary conditions,

F (x) = F (0) +

x

N

[F (N) − F (0)].

One nice thing about the last proof is that it was not necessary

to have already guessed the linear functions as solutions. The proof

produces these solutions.

1.2.2. Higher dimensions. We will generalize this result to higher

dimensions. We replace the interval {1,...,N} with an arbitrary

finite subset A of Zd. We let ∂A be the (outer) boundary of A defined

by

∂A = {z ∈

Zd

\ A : dist(z, A) = 1},

and we let A = A ∪ ∂A be the “closure” of A.

Figure 3. The white dots are A and the black dots are ∂A

♦

The term closure may seem strange, but in the continuous analogue,

A will be an open set, ∂A its topological boundary and

A = A ∪ ∂A its

topological closure.

We define the linear operators Q, L on functions by

QF (x) =

1

2d

y∈Zd,|x−y|=1

F (y),

LF (x) = (Q − I)F (x) =

1

2d

y∈Zd,|x−y|=1

[F (y) − F (x)].