interpolating between Markov and Chernoff

The function

$$h_{\alpha }(u)=\{\begin{array}{ll}1\{u\ge 0\},& \alpha =0,\\ (1+u/\alpha {)}_{+}^{\alpha },& \alpha \in (0,\infty ),\\ e^{\alpha },& \alpha =\infty ,\end{array}$$

is nondecreasing in $\alpha$ and $u$ (and continuous in $\alpha$ for $u\ge 0$). Therefore, for any random variable $X$,

$$\mathbb{P}(X\ge t)=\mathbb{E}1\{\lambda (X-t)\ge 0\}\le \mathbb{E}{\left(1+\frac{\lambda (X-t)}{\alpha }\right)}_{+}^{\alpha }\le \mathbb{E}{e}^{\lambda (X-t)}.$$

Thus, we see that the Chernoff method corresponds to the case $\alpha =\infty$ and Markov’s inequality corresponds to $\alpha =0$. Considering other values of $\alpha$ can thus get us tighter inequalities than the Chernoff bound. Of course, for values of $\alpha$ in $(0,\infty )$ the bound is much less nicer to work with, especially for sums of random variables.

While the Chernoff method requires that all moments exist (at least in some neighborhood), this method does not require that. Similarly to concentration via convex optimization, because this method is tighter than Chernoff, if we really need tight concentration in practice we should try it.

This observation gives rise to Bentkus’ inequality, and bounds which deploy $h_{\alpha }(u)$ have come to be known as Bentkus-style bounds.