Need help on Cramér-Chernoff method in concentration inequalities

Question

I am reading up on the Cramér-Chernoff method in concentration inequalities. The idea is to use Markov's inequality and the monotonic transformation $\phi(t) = e^{\lambda t}$ where $\lambda \geq 0$.

Consider a non-negative random variable $Z$ with finite expectation. Then Markov's inequality implies $$ (1) \qquad \Pr(Z \geq t) = \Pr(\phi(Z) \geq \phi(t)) \leq \frac{\mathbb{E}e^{\lambda Z}}{e^{\lambda t}} $$ In the Cramér-Chernoff method, we continue by letting $$ \qquad \psi_Z(\lambda) = \log \mathbb{E} e^{\lambda Z} \quad \text{ for all } \lambda \geq 0, $$ then standard texts claim that we have $$ (2) \qquad \Pr(Z \geq t) \leq \exp \left( \inf_{\lambda \geq 0} ( \psi_Z(\lambda) - \lambda t ) \right). $$ For example, see page 7/22 of the lecture note http://users.math.uni-potsdam.de/~blanchard/lectures/lect_2.pdf. My question is: how we can obtain the last inequality?

I understand that since (1) is true for all $\lambda \geq 0$, we can have $$ \Pr(Z \geq t) \leq \inf_{\lambda \geq 0} \frac{\mathbb{E}e^{\lambda Z}}{e^{\lambda t}} = \inf_{\lambda \geq 0} \left( \mathbb{E} \exp (\lambda Z - \lambda t) \right), $$ but I am confused with how this can lead to (2).

I'd appreciate for any help. Thank you in advance.

Answer 1

This comes from the fact that $$\inf_{\lambda \geq 0} ( \psi_Z(\lambda) - \lambda t )=\inf_{\lambda \geq 0} \log \mathbb{E} e^{\lambda Z-\lambda t}$$ and that for all positive continuous function $f$, $\inf_{\lambda \geq 0}\log \left(f\left(\lambda\right)\right)=\log \left(\inf_{\lambda \geq 0}f\left(\lambda\right)\right)$.

Answer 2

Starting from your $(1)$, we obtain

\begin{align} \mathrm{Pr}(Z \ge t) &\le \inf_{\lambda \ge 0}\frac{\mathbb Ee^{\lambda Z}}{e^{\lambda t}} \\ &= \exp\log \left\{\inf_{\lambda \ge 0}\frac {\mathbb Ee^{\lambda Z}}{e^{\lambda t}}\right\} \\ &= \exp \inf_{\lambda \ge 0}\left\{\log\frac {\mathbb Ee^{\lambda Z}}{e^{\lambda t}}\right\} \\ &= \exp \inf_{\lambda\ge 0}\left\{\log\mathbb E e^{\lambda Z} - \log e^{\lambda t}\right\} \\ &= \exp \inf_{\lambda\ge 0}\Big\{\underbrace{\log\mathbb E e^{\lambda Z}}_{=\psi_Z(\lambda)} - {\lambda t}\Big\}, \\ \end{align} where we use that $\exp \log x = x$, the fact that the logarithm does not change the supremum / infimum of a positive continuous function, and a rule of the logarithm, so that one arrives at $(2)$.

While the link does not seem to be working any longer, there is the book [Boucheron, 2013], which has more information on the above method and a lot more information on concentration inequalities in general.

Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence. Oxford university press.