The Chernoff bound is an exponential upper bound on the tail probability of a random variable. If the moment-generating function of 
is finite for some 
, then Markov's inequality
applied to 
gives
 |
The value of 
is chosen to make the right-hand side as small as possible.
Applying the same argument to 
gives a lower tail probability
bound. For a sum of independent random variables,
the moment-generating function factors into a product,
making the bound especially useful for showing that sums are exponentially unlikely
to differ greatly from their expectation values.
