II. SIMPLE EXPLANATIONS OF KEY IDEAS IN ORDINAL OPTIMIZATION



II.3. THE CHERNOFF BOUND EXPLAINED

We are interested in finding the probability of a random variable x exceeding certain value V, i.e., P(x >= V). Let us define another random variable YV such that

YV = 1 if x >= V
YV = 0 if x < V

Notice that E[YV] = Prob(x >= V).
Then elementary argument (see figure below) shows that for all s > 0.

esx >= esVYV

Thus,

E[esx] >= esV E[YV] = esV Prob(x >= V)
=> Prob(x >= V) <= e-sV E[esx], for all s >= 0

which is known as the Chernoff Bound. Furthermore,

Prob(x >= V) <= mins>=0 e-sV E[esx]
Prob(x >= V) <= mins>=0 exp{-sV + log E[esx]}

and we can define the rate function

R(s) = sups>=0 {sV - log E[esx]}

finally yielding

Prob(x >= V) <= exp[-R(s)]

i.e., the probability that a random variable is outside some set decreases exponentially fast as a function of the size of the set (V in this case).


To Next Slide / To Table of Content