1.1. Simple random walk 13

returns to the origin infinitely often. If d ≥ 3, the random walk is

transient, i.e., with probability one it returns to the origin only finitely

often. Also,

P{Sn = 0 for all n 0} 0 if d ≥ 3.

1.1.6. Notes about probability. We have already implicitly used

some facts about probability. Let us be more explicit about some of

the rules of probability. A sample space or probability space is a set

Ω and events are a collection of subsets of Ω including ∅ and Ω. A

probability P is a function from events to [0, 1] satisfying P(Ω) = 1

and the following countable additivity rule:

• If E1,E2,... are disjoint (mutually exclusive) events, then

P

∞

n=1

En =

∞

n=1

P(En).

We do not assume that P is defined for every subset of Ω, but we do

assume that the collection of events is closed under countable unions

and “complementation”, i.e., if E1,E2,... are events so are Ej and

Ω \ Ej.

♦

The assumptions about probability are exactly the assumptions used

in measure theory to define a measure. We will not discuss the diﬃculties

involved in proving such a probability exists. In order to do many things in

probability rigorously, one needs to use the theory of Lebesgue integration. We

will not worry about this in this book.

We do want to discuss one important lemma that probabilists use

all the time. It is very easy, but it has a name. (It is very common for

mathematicians to assign names to lemmas that are used frequently

even if they are very simple—this way one can refer to them easily.)

Lemma 1.3 (Borel-Cantelli Lemma). Suppose E1,E2,... is a collec-

tion of events such that

∞

n=1

P(En) ∞.

Then with probability one at most finitely many of the events occur.