32 1. Random Walk and Discrete Heat Equation

Example 1.11. Suppose that A is the “discrete ball” of radius r

about the origin,

A = {x ∈

Zd

: |x| r}.

Then every y ∈ ∂A satisfies r ≤ |y| r + 1. Suppose we start the

random walk at the origin. Then,

r2

≤ E[TA] (r +

1)2.

For any y ∈ A, let Vy denote the number of visits to y before

leaving A,

Vy =

TA−1

n=0

1{Sn = y} =

∞

n=0

1{Sn = y, TA n}.

Here we again use the indicator function notation. Note that

E[Vy | S0 = x] =

∞

n=0

P{Sn = y, TA n | S0 = x} =

∞

n=0

pn(x, y; A).

This quantity is of suﬃcient interest that it is given a name. The

Green’s function GA(x, y) is the function on A × A given by

GA(x, y) = E[Vy | S0 = x] =

∞

n=0

pn(x, y; A).

We define GA(x, y) = 0 if x ∈ A or y ∈ A. The Green’s function

satisfies GA(x, y) = GA(y, x). This is not immediately obvious from

the first equality but follows from the symmetry of pn(x, y; A). If we

fix y ∈ A, then the function f(x) = GA(x, y) satisfies the following:

Lf(y) = −1,

Lf(x) = 0, x ∈ A \ {y},

f(x) = 0, x ∈ ∂A.

Note that

TA =

y∈A

Vy,

and hence

E[TA | S0 = x] =

y∈A

GA(x, y).