Exercise 2.11: Upper and Lower Bounds for Gaussian Maxima
Without loss of generality, assume \(\sigma = 1\). Set \(X = X_1\).
(a)
Use the layer cake trick, but note that the tail bound is not integrable at the origin: \begin{align} \E[Z_n] &= \int_0^\infty \P(Z_n > u) \isd u \newline &\le c + n \int_c^\infty \P(|X| > u) \isd u \newline &\le c + 4n \int_c^\infty \frac{1}{\sqrt{2 \pi}} \frac{1}{u} e^{-\frac12 u^2} \isd u \newline &\le c + \frac{4n}{c} \int_c^\infty \frac{1}{\sqrt{2 \pi}} e^{-\frac12 u^2} \isd u \newline &\le c + \sqrt{\frac{2}{\pi}} \frac{4n}{c^2} e^{-\frac12 c^2}. \end{align} Set \(c = \sqrt{2 \log(n)}\). Then \begin{equation} \E[Z_n] \le \sqrt{2 \log(n)} + \sqrt{\frac{2}{\pi}} \frac{2}{\log(n)}, \end{equation} which is even stronger.
(b)
Attempt the following crude bound: \begin{equation} \E[Z_n] \ge \P(\text{some $|X_i| \ge \sqrt{c\log(n)}$}) \sqrt{c\log(n)}. \end{equation} We have that \begin{equation} \P(\text{some $|X_i| \ge \sqrt{c\log(n)}$}) = 1 - \P(|X| \le \sqrt{c\log(n)})^n = 1 - (1 - 2 Q(\sqrt{c\log(n)}))^n \end{equation} where \(Q(x) = \P(X \ge x)\). Consider \(c = 1\). Then, for \(n \ge 5\), it is true that \(Q(\sqrt{\log(n)}) \ge 1/(2n)\) (e.g., check visually), so \begin{equation} \E[Z_n] \ge (1 - (1 - 1/n)^n) \sqrt{\log(n)} \ge (1 - e^{-1})\sqrt{\log(n)}. \end{equation}
This misses the result by a constant \(\sqrt{2}\).
(c)
Attempt the layer cake trick: \begin{equation} \E[Z_n] = \int_0^\infty \P(Z_n > u) \isd u = \int_0^\infty (1 - (1 - 2 Q(u))^n) \isd u \end{equation} Note that, for every \(u \in \R\), \begin{equation} 1 - (1 - u/n)^n \downarrow 1 - \exp(-u). \end{equation} Therefore, \begin{equation} \E[Z_n] \ge \int_0^\infty (1 - e^{-2nQ(u)}) \isd u. \end{equation} For positive sequences \((a_n)_{n=1}^\infty\) and \((b_n)_{n=1}^\infty\), consider \begin{equation} \frac{\E[Z_n]}{a_n} \ge \int_0^\infty \frac{1 - e^{-2nQ(u)}}{a_n} \isd u \overset{(u = a_n v + b_n)}{=} \int_{-b_n/a_n}^\infty (1 - e^{-2nQ(a_n v + b_n)}) \isd v. \end{equation} We will choose \(a_n \to \infty\) and \(b_n \to 0\). Then Fatou’s lemma can be used to bring the limit inside: \begin{equation} \liminf_{n \to \infty} \frac{\E[Z_n]}{a_n} \ge \int_0^\infty \parens{1 - \exp\parens{ -2 \liminf_{n \to \infty} n Q(a_n v + b_n) }} \isd v. \end{equation} With \(a_n = \sqrt{2 \log(n)}\) and \(b_n = 1/a_n\), we will show that \begin{equation} n Q(a_n v + b_n) \to \begin{cases} \infty & \text{if $v < 1$,} \newline 0 & \text{if $v > 1$}, \end{cases} \end{equation} which immediately yields \begin{equation} \liminf_{n \to \infty} \frac{\E[Z_n]}{\sqrt{2 \log(n)}} \ge 1. \end{equation}
Use \(f(x) \sim g(x)\) to denote \begin{equation} 0 < \lim_{x \to \infty} \frac{f(x)}{g(x)} < \infty. \end{equation} Then, using that \(a_nv + b_n \to \infty\), \(Q(x) \sim \frac1x \phi(x)\) gives \begin{equation} n Q(a_n v + b_n) \sim \frac{n}{a_n v + b_n} \phi(a_n v + b_n). \end{equation} Expand \begin{equation} \phi(a_n v + b_n) \propto \exp\parens{ -\frac12a_n^2 v^2 + a_n b_n v - \frac12 b_n^2 v^2 } \sim e^{-\frac12 a_n^2 v^2}, \end{equation} since \(b_n = 1/a_n\) and \(b_n \to 0\). Hence \begin{equation} n Q(a_n v + b_n) \sim \frac{n}{a_n v + b_n} e^{-a_n^2 v^2} = \frac{n^{1-v^2}}{a_n v + b_n} \sim \frac{n^{1-v^2}}{a_n v} \propto \frac{n^{1-v^2}}{\sqrt{2 \log(n)}}, \end{equation} again using that \(b_n \to 0\). The result is now clear.