Exercise 2.12: Upper Bounds for Sub-Gaussian Maxima
(a)
For any \(\lambda > 0\), we can use the convexity of the exponential function to obtain \begin{align} \exp \lbrace \lambda \E [ \max_{i \in [n]} X_i ] \rbrace \leq \E [ \exp \lbrace \lambda \max_{i \in [n]} X_i \rbrace ] \, , \end{align} by Jensen’s inequality. Using the monotonicity of the exponential \begin{align} \E [ \exp \lbrace \lambda \max_{i \in [n]} X_i \rbrace ] = \E [ \max_{i \in [n]} e^{\lambda X_i}] \leq \sum_{i = 1}^n \E [e^{\lambda X_i}] \leq n e^{\frac{\lambda^2 \sigma^2}{2}} \, . \end{align} Hence \(\E [\max_{i \in [n]} X_i] \leq \frac{\log n}{\lambda} + \lambda \frac{\sigma^2}{2}\) and optimising over \(\lambda > 0\) yields \(\lambda = \frac{\sqrt{2 \log n}}{\sigma}\); substituting \begin{align} \E [\max_{i \in [n]} X_i] \leq \frac{\sigma}{\sqrt{2}} \sqrt{\log n} + \frac{\sigma}{\sqrt{2}} \sqrt{\log n} = \sqrt{2 \sigma^2 \log n} \, . \end{align}
(b)
Note that (a) does not assume independence between individual \(X_i\). The result thus follows by \begin{align} \max_{i \in [n]} |X_i| = \max \lbrace X_1, \ldots , X_n , - X_1 , \ldots , - X_n \rbrace \, . \end{align}