Canonical: https://knowlpedia.com/probability/chernoff-bound/

# Chernoff bound

Exponential tail bound using moment generating functions.

**Chernoff bound:** Let \(X\) be a [random variable](https://knowlpedia.com/probability/random-variable/). Suppose \(\mathbb{E}[e^{tX}]<\infty\) for some \(t>0\). Then for every real \(a\) and every \(t>0\) for which the expectation is finite,
\[
\mathbb{P}(X\ge a)\le e^{-ta}\,\mathbb{E}\!\left[e^{tX}\right].
\]

Similarly, if \(\mathbb{E}[e^{-tX}]<\infty\) for some \(t>0\), then for every real \(a\) and every such \(t\),
\[
\mathbb{P}(X\le a)\le e^{ta}\,\mathbb{E}\!\left[e^{-tX}\right].
\]

## Equivalent characterizations

Equivalently,
\[
\mathbb{P}(X\ge a)\le \inf_{t>0} \; e^{-ta}\,\mathbb{E}\!\left[e^{tX}\right].
\]

## Remarks

This bound is obtained by applying [Markov's inequality](https://knowlpedia.com/probability/markov-inequality/) to the nonnegative random variable \(e^{tX}\), and it is naturally expressed in terms of the [moment generating function](https://knowlpedia.com/probability/moment-generating-function/) of \(X\).
