Chernoff method

The Chernoff method, also called the Cramer-Chernoff method, applies Markov’s inequality to the nonnegative random variable $e^{\lambda X}$, and then chooses $\lambda$ to optimize the bound. This often results in tighter bounds and concentration inequalities than working with the random variable directly.

In particular, for a random variable $X$, Markov’s inequality gives that

$$\mathbb{P}(X\ge t)=\mathbb{P}(e^{\lambda X}\ge e^{\lambda t})\le e^{-\lambda t}\mathbb{E}[e^{\lambda X}].$$

This holds for all $\lambda >0$, so we obtain the bound

$$\mathbb{P}(X\ge t)\le \underset{\lambda >0}{\inf }{e}^{-\lambda t}\mathbb{E}[e^{\lambda X}]=\underset{\lambda >0}{\inf }{e}^{-\lambda t}{M}_X(\lambda ),$$

where $M_X$ is the MGF of $X$. If we place distributional assumptions on $X$ (eg bounded, sub-Gaussianity), then we can solve for the optimal value of $\lambda$. If $X={\sum }_{i\le n}{X}_i$ is the sum of iid observations, then $\mathbb{E}[e^{\lambda X}]={\prod }_i\mathbb{E}[e^{\lambda X_i}]=n\mathbb{E}[e^{\lambda X_1}]$. This makes the Chernoff particularly attractive under independence assumptions, even though it is not optimal (see below).

The Chernoff method is often written in terms of the Cramer transform of $X$ (which is why it’s often called the Cramer-Chernoff method), which is

$${\psi }_X^{\ast }(t)=\underset{\lambda \ge 0}{\sup }(\lambda t-{\psi }_X(\lambda )),\text{where}{\psi }_X(\lambda )=\log \mathbb{E}{e}^{\lambda Z}.$$

This is also often called the Fenchel-Legendre transform. This gives,

$$\mathbb{P}(X\ge t)\le \exp (-{\psi }_X^{\ast }(t)),$$

which leads us to studying and bounding the function ${\psi }_X^{\ast }(t)$.

Optimality

The Chernoff method is very convenient hence widely deployed, but it’s not optimal. We can see this in the case of Hoeffding’s bound, which is missing a factor of $1/t$ in the exponent from what we expect from the CLT. (See The missing factor in Hoeffding’s inequalities by Talagrand).

More generally, the method of moments for concentration beats the Chernoff bound (when all moments exist), and the optimization approach to concentration (concentration via convex optimization) will give the tightest results if the convex program can be solved. See also interpolating between Markov and Chernoff, which is tighter than the Chernoff method but also less computationally convenient.

However, the Chernoff method is optimal is one sense. If $X_1,\dots ,X_n$ are iid mean zero, $S_n={\sum }_i{X}_i$, and for all $t\ge 0$,

$$\mathbb{P}(S_n\ge nt)\le Q^n(t),$$

then

$$Q(t)\ge \underset{\lambda \ge 0}{\inf }\mathbb{E}[\exp (\lambda (X-t))].$$

That, we have a bound which uses the product structure of the observations (hence the power of $n$ on $Q(t)$), then the Chernoff method is optimal.