1.1. A review of probability theory 5

To assist in this, we will choose notation that avoids explicit use of set the-

oretic notation. For instance, the union of two events E, F will be denoted

E ∨ F rather than E ∪ F , and will often be referred to by a phrase such as

“the event that at least one of E or F holds”. Similarly, the intersection

E ∩ F will instead be denoted E ∧ F , or “the event that E and F both

hold”, and the complement Ω\E will instead be denoted E, or “the event

that E does not hold” or “the event that E fails”. In particular, the sure

event Ω can now be referred to without any explicit mention of the sample

space as ∅. We will continue to use the subset notation E ⊂ F (since the

notation E ≤ F may cause confusion), but refer to this statement as “E is

contained in F ” or “E implies F ” or “E holds only if F holds” rather than

“E is a subset of F ”, again to downplay the role of set theory in modeling

these events.

We record the trivial but fundamental union bound

(1.1) P(

i

Ei) ≤

i

P(Ei)

for any finite or countably infinite collection of events Ei. Taking comple-

ments, we see that if each event Ei fails with probability at most εi, then

the joint event

i

Ei fails with probability at most

∑

i

εi. Thus, if one wants

to ensure that all the events Ei hold at once with a reasonable probability,

one can try to do this by showing that the failure rate of the individual

Ei is small compared to the number of events one is controlling. This is

a reasonably eﬃcient strategy so long as one expects the events Ei to be

genuinely “different” from each other; if there are plenty of repetitions, then

the union bound is poor (consider for instance the extreme case when Ei

does not even depend on i).

We will sometimes refer to use of the union bound to bound probabil-

ities as the zeroth moment method, to contrast it with the first moment

method, second moment method, exponential moment method, and Fourier

moment methods for bounding probabilities that we will encounter later in

this course; see (1.22) below for an explanation of the terminology “zeroth

moment method”.

Let us formalise some specific cases of the union bound that we will use

frequently in the course. In most of this course, there will be an integer

parameter n, which will often be going off to infinity, and upon which most

other quantities will depend; for instance, we will often be considering the

spectral properties of n × n random matrices.

Definition 1.1.2 (Asymptotic notation). We use X = O(Y ), Y = Ω(X),

X Y , or Y X to denote the estimate |X| ≤ CY for some C inde-

pendent of n and all n ≥ C. If we need C to depend on a parameter, e.g.,

C = Ck, we will indicate this by subscripts, e.g., X = Ok(Y ). We write