14 1. Random Walk and Discrete Heat Equation

Proof. Let A be the event that infinitely many of E1,E2,... occur.

For each integer N, A ⊂ AN where AN is the event that at least one

of the events EN , EN+1,... occurs. Then,

P(A) ≤ P(AN ) = P

∞

n=N

En ≤

∞

n=N

P(En);

but

∑

P(En) ∞ implies

lim

N→∞

∞

n=N

P(En) = 0.

Hence, P(A) = 0.

As an example, consider the simple random walk in

Zd,d

≥ 3 and

let En be the event that Sn = 0. Then, the estimates of the previous

section show that

∞

n=1

P(En) ∞,

and hence with probability one, only finitely many of the events En

occur. This says that with probability one, the random walk visits

the origin only finitely often.

1.2. Boundary value problems

1.2.1. One dimension: Gambler’s ruin. Suppose N is a positive

integer and a random walker starts at x ∈ {0, 1,...,N}. Let Sn

denote the position of the walker at time n. Suppose the walker stops

when the walker reaches 0 or N. To be more precise, let

T = min {n : Sn = 0 or N} .

Then the position of the walker at time n is given by

ˆ

S

n

= Sn∧T

where n ∧ T means the minimum of n and T . It is not hard to see

that with probability one, T ∞, i.e., eventually the walker will

reach 0 or N and then stop. Our goal is to try to figure out which

point it stops at. Define the function F : {0,...,N} → [0, 1] by

F (x) = P{ST = N | S0 = x}.