Chernoff bounds

Summary

The Chernoff bounds are a way of bounding the probability that a sum of independent random variables takes on extreme values. Compared with Chebyshev's inequality, it requires a stronger assumption (independence), but is a far tighter bound. They are commonly used to analyze randomized algorithms and PAC-learning methods.

Context

This concept has the prerequisites:

Goals

  • Give the general statement of Chernoff bounds in terms of moment generating functions
  • Derive the bound using Markov's inequality
  • Be able to use it to bound probabilities of extreme values
  • When would you use the Chernoff bound vs. the Chebyshev bound?

Core resources (we're sorry, we haven't finished tracking down resources for this concept yet)

Supplemental resources (the following are optional, but you may find them useful)

-Paid-

See also