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) ≥

1 −

CAn−A

for some CA independent of n).

(iv) An event E holds with high probability if it holds with probability

1 −

O(n−c)

for some c 0 independent of n (i.e., one has P(E) ≥

1 −

Cn−c

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

surely, then

α

Eα holds almost surely.

(iii) If Eα is a family of events of polynomial cardinality (i.e., cardinality

O(nO(1)))

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-

dinality

O(no(1)))

which hold with uniformly high probability, the

α

Eα holds with high probability. (In particular, the cardinality

can be polylogarithmic in size,

O(logO(1)

n).)