HDS

Exercise 2.18: Orlicz Norms

chapter 2 Chernoff bound layer cake

(a)

By the Chernoff bound \begin{align} \P (|X| > t) &\leq \inf_{\lambda > 0} e^{- \lambda^{-q} t^q} \E [e^{\lambda^{-q}|X|^q}] \newline &= \inf_{\lambda > 0} e^{- \lambda^{-q} t^q} \lbrace 1 + \E [\psi_q (\lambda^{-1} |X|)] \rbrace \newline &\leq 2 e^{- \| X \|_{\psi_q}^{-q} t^q } \, , \end{align} where the last inequality follows by the definition of \(\| X \|_{\psi_q}\).

(b)

Since \(e^{t^{-q} |X|^q} - 1 \geq 0\), we can use the layer cake trick \begin{align} \E [ e^{t^{-q} |X|^q} - 1 ] &= \int_0^\infty \P (e^{t^{-q} |X|^q} - 1 > u) \, \sd u \newline &= \int_0^\infty \P (|X| > t \log^{1 / q}(1 + u)) \, \sd u \newline &\leq c_1 \int_0^\infty \exp \lbrace - c_2 t^q \log (1 + u) \rbrace \, \sd u \newline &\overset{\text{(i)}}{=} c_1 \int_0^\infty \exp \lbrace (1 - c_2 t^q)v \rbrace \, \sd v \newline &= \frac{c_1}{c_2 t^q - 1} \overset{\text{(ii)}}{<} \infty \, , \end{align} where (i) is by substitution of \(v = \log(1 + u)\), and (ii) holds for any \(t \neq c_2^{- 1 / q}\).

Published on 27 August 2020.