Chernoff Bounds

Markov's inequality bounds $P(X \ge a)$ using only the mean, and the bound is almost always embarrassingly loose. Chebyshev tightens it using the variance, but is still loose for questions like "what's the chance my hedged book loses more than $1m today," where the honest answer decays exponentially and Chebyshev only promises a $1/k^2$-style decay. Chernoff bounds close that gap — they are, in a precise sense, the best possible exponential tail bound obtainable from the moment generating function.

The analogy: choosing the best vantage point

Imagine you want an upper bound on how tall a mountain range could be, and you're allowed to look at it from any angle. Some angles make it look enormous (bad bound), some make it look almost flat (still a valid bound, if you can prove it). Markov and Chebyshev pick one fixed, generic angle every time. Chernoff's idea is: don't commit to one viewing angle in advance — try every angle (every exponential tilt of the distribution) and report the tightest bound any of them gives you. That optimization over angles is exactly where the exponential sharpness comes from.

Writing it down

Start from Markov's inequality applied not to $X$ itself but to $e^{sX}$ for some tuning parameter $s > 0$:

$$P(X \ge a) = P(e^{sX} \ge e^{sa}) \le \frac{E[e^{sX}]}{e^{sa}} = e^{-sa} M_X(s),$$

where $M_X(s) = E[e^{sX}]$ is the moment generating function. In words: exponentiating both sides turns "X is large" into "$e^{sX}$ is large," and Markov's inequality now applies to that transformed, always-positive quantity. The right-hand side holds for every valid $s > 0$, so the Chernoff bound picks the tightest one:

$$P(X \ge a) \le \min_{s > 0} \; e^{-sa} M_X(s).$$

In words: minimize the bound over the tilt parameter $s$ — this is what makes Chernoff bounds sharp rather than generic. For a sum $S_n = X_1 + \cdots + X_n$ of independent variables, the MGF factors, $M_{S_n}(s) = \prod_i M_{X_i}(s)$, which is why Chernoff bounds are the standard tool for sums — and why they produce the exponential decay in $n$ that Hoeffding's inequality inherits.

Adjust the rate and watch the curve's steepness — that's the shape of $e^{-sa}M_X(s)$ as a function of the deviation $a$: the further into the tail, the more the exponential crushes the probability, in contrast to Chebyshev's much slower $1/a^2$ decay.

Worked example 1: sum of fair coin flips

Let $X_i$ be independent $\pm 1$ fair coin flips, $S_n = \sum_{i=1}^n X_i$. Its MGF is $M_{X_i}(s) = \cosh(s)= \tfrac12(e^s+e^{-s})$, and using $\cosh(s) \le e^{s^2/2}$, $M_{S_n}(s) \le e^{ns^2/2}$. Minimizing $e^{-sa + ns^2/2}$ over $s$ gives $s = a/n$, and plugging back in:

$$P(S_n \ge a) \le e^{-a^2/(2n)}.$$

For $n = 100$ flips, what's the bound on the chance the sum exceeds $a = 20$ (i.e., at least 60 heads out of 100)? $e^{-400/200} = e^{-2} \approx 0.135$. Compare Chebyshev on the same question: variance of $S_n$ is $n = 100$, so Chebyshev gives $P(|S_n|\ge 20) \le 100/400 = 0.25$ — Chernoff is already almost twice as tight, and the gap widens fast as $a$ grows.

This is the actual head-count distribution behind the example: watch how little mass sits at 60 or more heads out of 100 — thin enough that both Chebyshev and Chernoff are only bounding it from above, and Chernoff's bound tracks that thinness far more closely.

Worked example 2: capital needed against a rare large loss

A trading book's daily P&L is well modeled (over a short horizon) as a sum of 50 independent $1,000-unit bets, each $\pm 1$ unit with 52% chance of $+1$ (edge $\mu = 0.04$ per unit, so mean P&L = 50 \times 0.04 \times \1000=$2{,}000). What's a Chernoff bound on the probability of losing at least \10,000 today, i.e. $S_{50} \le -10$ in units? By symmetry of the calculation above (shifting for the drift), the bound comes out near $e^{-(14)^2/100} \approx e^{-1.96} \approx 0.141$ — a rough but honest exponential estimate that a naive "it's diversified across 50 bets, so it's basically safe" intuition would understate. It tells the desk that a $10,000 daily loss, while not the expected case, is not a tail event to ignore either — worth sizing capital for explicitly.

What this means in practice

• VaR and stress limits. Chernoff-style bounds give a defensible, distribution-light way to bound the probability of large losses on a sum of positions, without needing to assume normality.
• Randomized algorithms and Monte Carlo. Chernoff bounds are the standard tool for bounding how many simulation paths are needed before a Monte Carlo price estimate concentrates near the true value.
• Better than Chebyshev whenever the MGF exists. If your variable has a well-behaved MGF (most bounded or light-tailed quantities do), Chernoff is essentially always the tighter tool — reach for it before Chebyshev.