Lower bound for expectation of maximum absolute value of standard normal random variables I am looking for the simplest possible proof to show that for iid $X_i \sim \mathcal{N}(0,1)$, there is a $c > 0$ such that:
$$\mathbb{E}\left( \max_{1 \leq i \leq n} |X_i| \right) \geq c \sqrt{\log(n)}$$
I've tried a lot on my own based on Chernoff bounds and bounding the tail probabilities of a standard normal, yet I haven't been able to string it together consistently. Also, proofs like the one of Theorem 3 here: https://arxiv.org/pdf/1511.02176.pdf are way too complicated for my purpose. I would greatly appreciate any input!
 A: To solve problems with maxima of iid random variables, the internal automatic pilot should tell us to apply the equality:
$$\mathbb{P}\left( \max_{1 \leq i \leq n} |X_i| \geq x \right) = 1 - \left( \mathbb{P}( |X_1| < x) \right)^n.$$
Following this idea, we rewrite the quantity of interest, by integration by parts, as
$$\mathbb{E} \left[  \max_{1 \leq i \leq n} |X_i| \right] = \int_0^\infty \mathbb{P} \left( \max_{1 \leq i \leq n} |X_i| \geq x \right) dx.$$
Before plugging in the autopilot identity, we should also make sure to know what happens to the term $\mathbb{P}(| X_1 |< x)= 1 - \mathbb{P}(|X_1| \geq x)$. Since we know that the random variables are normalized Gaussians:
$$\mathbb{P}(|X_1| \geq x) = \frac{2}{\sqrt{2\pi}}\int_0^{\infty} e^{-\frac{|y+x|^2}{2}} dy \leq e^{- |x|^2}.$$
But this bound goes in the wrong direction (it will lead us to an upper bound on the average, not a lower bound. Instead, we will use
$$\mathbb{P}(|X_1| \geq x) \geq \frac{2}{\sqrt{2\pi}}\int_0^{1} e^{-\frac{|y+x|^2}{2}} dy \geq c e^{- |x|^2},$$
for some $c>0$. In this way we find that
\begin{align*}
\mathbb{E} \left[  \max_{1 \leq i \leq n} |X_i| \right] & = \int_0^\infty 1 - \left( 1 - \mathbb{P}( |X_1| \geq x) \right)^n d x \\
& \geq \int_0^\infty 1 - \left( 1 - ce^{-|x|^2} \right)^n d x.
\end{align*}
We are almost done. We see that the integrand is close to $1$ for $0 < x \ll 1$ and close to $0$ for $x \gg 1$. Bernoulli's formula for the exponential tells us that the location at which we pass from $0$ to $1$ (the front, so to speak) is at rughly $x\sim \sqrt{\log(n)}.$ Of course we have no clue how steep the front is. Luckily, we do not need any particular understanding: a magical change of variables $x =\sqrt{\log(n)} u$ removes all problems.
\begin{align*} \int_0^\infty 1 - \left( 1 - ce^{-|x|^2} \right)^n d x & = \sqrt{log(n)} \int_0^\infty 1 - \left( 1 - \frac{c}{n^{u^2}} \right)^n d u \\
& \geq\sqrt{log(n)} \int_0^\infty 1- \alpha^{\frac{1}{u^2}} du,
\end{align*}
where $\alpha \in (0, 1)$ depends on $c$, but not on $n$ or $u$. Now, for large $u$, where exists a $\beta > 0$ such that $\alpha^{\frac{1}{u^2}} \leq 1 - \beta \frac{1}{u^2}$ (this is a Taylor expansion). Overall:
\begin{align*} \mathbb{E} \left[  \max_{1 \leq i \leq n} |X_i| \right] & \geq \sqrt{log(n)} \int_0^\infty \frac{\beta}{u^2} du,
\end{align*}
which proves the lower bound.
