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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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