---
tag: 014PEBGDYF
kind: statement
role: theorem
name: Chernoff bound
msc: ["60E15"]
uses: [05PWWHYBX5, 0NNRNGKMFM]
sources:
  - url: https://en.wikipedia.org/wiki/Chernoff_bound
    locator: Generic Chernoff bounds
same_as:
  wikidata: Q1070305
  wikipedia: Chernoff bound
---

## Statement

Let $X$ be a real random variable with [[moment-generating function|0NNRNGKMFM]] $M_X(t) = E[e^{tX}]$, and let $a \in \mathbb{R}$. Then
$$P(X \ge a) \le \inf_{t > 0} e^{-ta} M_X(t).$$

## Remarks

Proof: for each $t > 0$, $\{X \ge a\} = \{e^{tX} \ge e^{ta}\}$. [[Markov's inequality|05PWWHYBX5]] gives $P(X \ge a) \le e^{-ta} E[e^{tX}]$. Then take the infimum over $t$.
For a sum $S$ of independent $X_i$, $M_S = \prod_i M_{X_i}$. So the bound becomes $\inf_{t > 0} e^{-ta} \prod_i M_{X_i}(t)$, which decreases exponentially in many cases.
For $S \sim \operatorname{Bin}(n, p)$ with mean $\mu = np$ and $0 < \delta$, a standard consequence is $P(S \ge (1 + \delta)\mu) \le \left(e^{\delta} / (1 + \delta)^{1 + \delta}\right)^{\mu}$.

## History

The bound is named after Herman Chernoff.

## Explanations

### L1 human

The Chernoff bound gives tail estimates that decrease very fast, often exponentially.
It is much stronger than Chebyshev's inequality for sums of many independent terms, such as the number of heads in many tosses.