1.1. A review of probability theory 7

(v) If Eα is a family of events of uniformly bounded cardinality (i.e.,

cardinality O(1)) which each hold asymptotically almost surely, then

α

Eα holds asymptotically almost surely. (Note that uniformity

of asymptotic almost sureness is automatic when the cardinality is

bounded.)

Note how as the certainty of an event gets stronger, the number of

times one can apply the union bound increases. In particular, holding with

overwhelming probability is practically as good as holding surely or almost

surely in many of our applications (except when one has to deal with the

metric entropy of an n-dimensional system, which can be exponentially large,

and will thus require a certain amount of caution).

1.1.2. Random variables. An event E can be in just one of two states:

the event can hold or fail, with some probability assigned to each. But

we will usually need to consider the more general class of random variables

which can be in multiple states.

Definition 1.1.4 (Random variable). Let R = (R, R) be a measurable space

(i.e., a set R, equipped with a σ-algebra of subsets of R). A random variable

taking values in R (or an R-valued random variable) is a measurable map X

from the sample space to R, i.e., a function X : Ω → R such that

X−1(S)

is an event for every S ∈ R.

As the notion of a random variable involves the sample space, one has

to pause to check that it invariant under extensions before one can assert

that it is a probabilistic concept. But this is clear: if X : Ω → R is a

random variable, and π : Ω → Ω is an extension of Ω, then X := X ◦ π is

also a random variable, which generates the same events in the sense that

(X

)−1(S)

=

π−1(X−1(S))

for every S ∈ R.

At this point let us make the convenient convention (which we have,

in fact, been implicitly using already) that an event is identified with the

predicate which is true on the event set and false outside of the event set.

Thus, for instance, the event

X−1(S)

could be identified with the predicate

“X ∈ S”; this is preferable to the set-theoretic notation {ω ∈ Ω : X(ω) ∈ S},

as it does not require explicit reference to the sample space and is thus more

obviously a probabilistic notion. We will often omit the quotes when it is

safe to do so, for instance, P(X ∈ S) is shorthand for P(“X ∈ S”).

Remark 1.1.5. On occasion, we will have to deal with almost surely defined

random variables, which are only defined on a subset Ω of Ω of full prob-

ability. However, much as measure theory and integration theory is largely

unaffected by modification on sets of measure zero, many probabilistic con-

cepts, in particular, probability, distribution, and expectation, are similarly