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 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 is an arbitrary family of events that each hold surely, then
α
holds surely.
(ii) If is an at most countable family of events that each hold almost
surely, then
α
holds almost surely.
(iii) If is a family of events of polynomial cardinality (i.e., cardinality
O(nO(1)))
which hold with uniformly overwhelming probability, the
α
holds with overwhelming probability.
(iv) If is a family of events of sub-polynomial cardinality (i.e., car-
dinality
O(no(1)))
which hold with uniformly high probability, the
α
holds with high probability. (In particular, the cardinality
can be polylogarithmic in size,
O(logO(1)
n).)
Previous Page Next Page