1.2. Boundary value problems 17

where

A =

⎡

⎢

⎢

⎢

⎢

⎢

⎢

⎢

⎢

⎣

−1

1

2

0 0 · · · 0 0

1

2

−1

1

2

0 · · · 0 0

0

1

2

−1

1

2

· · · 0 0

.

.

.

0 0 0 0 · · · −1

1

2

0 0 0 0 · · · 1

2

−1

⎤

⎥

⎥

⎥

⎥

⎥

⎥

⎥

⎥

⎦

, w =

⎡

⎢

⎢

⎢

⎢

⎢

⎢

⎢

⎢

⎣

−

F (0)

2

0

0

.

.

.

0

−

F (N)

2

⎤

⎥

⎥

⎥

⎥

⎥

⎥

⎥

⎥

⎦

.

If we prove that A is invertible, then the unique solution is v =

A−1w.

To prove invertibility it suﬃces to show that Av = 0 has a unique

solution and this can be done by an argument as in the previous proof.

Proof 4. Suppose F is a solution to (1.8). Let Sn

be the random

walk starting at x. We claim that for all n, E[F (Sn∧T )] = F (x).

We will show this by induction. For n = 0, F (S0) = F (x) and

hence E[F (S0)] = F (x). To do the inductive step, we use a rule for

expectation in terms of conditional expectations:

E[F (S(n+1)∧T )] =

N

y=0

P{Sn∧T = y} E[F (S(n+1)∧T ) | Sn∧T = y].

If y = 0 or y = N and Sn∧T = y, then S(n+1)∧T = y and hence

E[F (S(n+1)∧T ) | Sn∧T = y] = F (y). If 0 y x and Sn∧T = y, then

E[F (S(n+1)∧T ) | Sn∧T = y] =

1

2

F (y + 1) +

1

2

F (y − 1) = F (y).

Therefore,

E[F (S(n+1)∧T )] =

N

y=0

P{Sn∧T = y} F (y) = E[F (Sn∧T )] = F (x),

with the last equality holding by the inductive hypothesis. Therefore,

F (x) = lim

n→∞

E[F (Sn∧T )]

= lim

n→∞

N

y=0

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

= P{ST = 0} F (0) + P{ST = N} F (N)

= [1 − P{ST = N}] F (0) + P{ST = N} F (N).