Chernoff method

The 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$.

The Chernoff method is often written in terms of the Cramer transform of $X$ (hence often called in 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. We can write

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