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:
- independent random variables (The Chernoff bounds are statements about independent random variables.)
- moment generating functions (Chernoff bounds can be specified in terms of moment generating functions.)
- Markov and Chebyshev inequalities (Markov's inequality is used to prove the bound.)
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-
→ A First Course in Probability
An introductory probability textbook.
Location:
Section 8.5, "Other inequalities," from pages 450 to 453
See also
- Deriving the bounds
- Chernoff bounds are widely used in: