# 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: