Chernoff Bound¶

Theorem¶

Let $X$ be a random variable and $a\in\mathbb{R}$ $R$ . For every $t>0$ at which the MGF $M_X(t)$ is finite,

\begin{aligned} \mathbb{P}(X\geq a)\leq \mathrm{e}^{-ta}M_X(t). \end{aligned}

Optimizing over such $t>0$ gives the tightest bound. The optimization must stay within the region where the MGF is finite, and the infimum need not be attained.

Apply the Generalized Markov Inequality to the nonnegative variable $\mathrm{e}^{tX}$ at threshold $\mathrm{e}^{ta}$ . Its expectation is the Moment Generating Function $M_X(t)$ , giving the displayed bound.

Interpretation¶

An exponential transformation turns a tail probability into an MGF bound. For a fixed $t>0$ with $M_X(t)<\infty$ $\infty$ , the bound $\mathrm{e}^{-ta}M_X(t)$ decreases exponentially in the threshold $a$ , whereas the Markov and Chebyshev bounds decrease only like $1/a$ and $1/a^2$ .

The bound e to the minus 3t times the MGF, plotted for t between 0 and 1. Its minimum, about 0.406 at t = 2/3, lies well above the exact tail probability e to the minus 3, about 0.050, drawn as a line.

The figure plots the bound $\mathrm{e}^{-3t}M_X(t)=\mathrm{e}^{-3t}/(1-t)$ for $X\sim\operatorname{Exp}(1)$ and $a=3$ $3$ , the second Example. Every $t\in(0,1)$ gives a valid bound. The curve starts at $1$ for $t=0$ and grows without bound as $t\to1$ $1$ , where the MGF stops being finite. Its minimum, at $t=2/3$ $2/3$ , is $3\mathrm{e}^{-2}\approx0.406$ $0.406$ , still well above the exact tail $\mathrm{e}^{-3}\approx0.050$ $0.050$ .

Every $t>0$ gives a bound $\mathrm{e}^{-ta}M_X(t)$ (right). Move $t$ , or press the button, to find the $t$ that makes it smallest.

The free parameter $t$ is a trade-off: larger $t$ makes $\mathrm{e}^{-ta}$ smaller but $M_X(t)$ larger. Setting the derivative of $-ta+\ln M_X(t)$ to zero gives the best $t$ in both Examples. Only $t>0$ is allowed in the upper-tail bound, because the Markov step needs a nondecreasing function; for $t<0$ the function $\mathrm{e}^{tx}$ is decreasing, and the same argument bounds the lower tail $\mathbb{P}(X\le a)$ instead.

The bound is at its strongest for sums. For i.i.d. terms, the MGF of an independent sum gives $\mathbb{P}(S_n\ge na)\le\bigl(\mathrm{e}^{-ta}M_{X_1}(t)\bigr)^n$ $(e^{- t a} M_{X_{1}} (t))^{n}$ . When the bracket is below $1$ , which a small $t>0$ achieves for $a>\mathbb{E}X_1$ if the MGF is finite near $0$ , the bound falls exponentially in $n$ , much faster than the Chebyshev bound, which decreases like $1/n$ .

Key Results¶

$\mathbb{P}(X\ge a)\le\inf_{\{t>0\colon M_X(t)<\infty\}}\mathrm{e}^{-ta}M_X(t)$ $in f_{{t > 0 : M_{X} (t) < \infty}} e^{- t a} M_{X} (t)$ .
For $t<0$ with finite MGF, $\mathbb{P}(X\le a)\le \mathrm{e}^{-ta}M_X(t)$ $e^{- t a} M_{X} (t)$ .

Examples¶

For $X\sim\operatorname{Pois}(2)$ and $a=4$ $4$ , choose $t=\log2$ $lo g 2$ : $\mathbb{P}(X\ge4)\le \mathrm{e}^{-4\log2+2(2-1)}=\mathrm{e}^2/16\approx0.4618$ $0.4618$ .
For $X\sim\operatorname{Exp}(1)$ and $a=3$ $3$ , choose $t=2/3$ $2/3$ : $\mathbb{P}(X\ge3)\le \mathrm{e}^{-2}/(1-2/3)=3\mathrm{e}^{-2}\approx0.4060$ $0.4060$ .

Prerequisites¶

Sources¶

Nicky van Foreest · Probability Distributions · Week 7

Aliases: Chernoff inequality, Chernoff's bound, Cramér–Chernoff bound Symbols: element of, infinity, real numbers

Last updated: 20 October 2026 03:02