3
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.