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(
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
Ei fails with probability at most

ε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 efficient 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
Previous Page Next Page