6 1. Preparatory material
X = o(Y ) if |X| ≤ c(n)Y for some c that goes to zero as n → ∞. We write
X ∼ Y or X = Θ(Y ) if X Y X.
Given an event E = En depending on such a parameter n, we have five
notions (in decreasing order of confidence) that an event is likely to hold:
(i) An event E holds surely (or is true) if it is equal to the sure event
(ii) An event E holds almost surely (or with full probability) if it occurs
with probability 1: P(E) = 1.
(iii) An event E holds with overwhelming probability if, for every fixed
A 0, it holds with probability 1−OA(n−A) (i.e., one has P(E) ≥
for some CA independent of n).
(iv) An event E holds with high probability if it holds with probability
for some c 0 independent of n (i.e., one has P(E) ≥
for some C independent of n).
(v) An event E holds asymptotically almost surely if it holds with prob-
ability 1−o(1), thus the probability of success goes to 1 in the limit
n → ∞.
Of course, all of these notions are probabilistic notions.
Given a family of events Eα depending on some parameter α, we say
that each event in the family holds with overwhelming probability uniformly
in α if the constant CA in the definition of overwhelming probability is
independent of α; one can similarly define uniformity in the concepts of
holding with high probability or asymptotic almost sure probability.
From the union bound (1.1) we immediately have
Lemma 1.1.3 (Union bound).
(i) If Eα is an arbitrary family of events that each hold surely, then
Eα holds surely.
(ii) If Eα is an at most countable family of events that each hold almost
Eα holds almost surely.
(iii) If Eα is a family of events of polynomial cardinality (i.e., cardinality
which hold with uniformly overwhelming probability, the
Eα holds with overwhelming probability.
(iv) If Eα is a family of events of sub-polynomial cardinality (i.e., car-
which hold with uniformly high probability, the
Eα holds with high probability. (In particular, the cardinality
can be polylogarithmic in size,