I'm strugging to find a neat solution to the following problem.
Let $X_1,\dots,X_N \sim N(0,1)$ and let $X = \max_i X_i$. Show that
$\mathbb{E}[X] \geq c \sqrt{\ln N}$
for some absolute constant $c$.
Combining the lower tail bound for standard Gaussians
$\mathbb{P} (X_i > a) \geq \frac{1}{\sqrt{2 \pi} a + 2} e^{-a^2/2}$
with the total expecation theorem $\mathbb{E}[X] = \mathbb{E}[X | X \geq a] \mathbb{P}(X \geq a) + \mathbb{E}[X | X < a]\mathbb{P}(X < a)$, I managed to prove the inequaility but it requeired a lot of tedious calculations.
Is there a simple and neat way to prove that lower bound?
I have seen a related post Expectation of the maximum of gaussian random variables, where the distribution of $X$ is derived, however I was not able to bound from below the expectation integral.
Many thanks in advance.
The way you said you proved the inequality is probably the only way to do it. It does not seem to require a lot of tedious calculations.
If $g$ is a standard Gaussian, then $$\hbox{Prob}\{g>t\}\geq (\frac{1}{t}-\frac{1}{t^3})e^{-t^2/2}$$ (See Feller, Vol. $1$, $3$rd edition, p. $175$) Hence there exists a positive $\beta>0$ (smaller than $1$) such that $$\hbox{Prob}\{g>\beta(\log n)^{1/2}\}\geq\frac{1}{n}$$ Now if $g_1,\dots,g_n$ are independent standard Gaussians, then using the previous inequality, we get $$\hbox{Prob}\{\max g_i \leq\beta(\log n)^{1/2}\}<(1-\frac{1}{n})^n\approx \frac{1}{e}$$ Hence $$\mathbb{E}(\max g_i)>\beta(\log n)^{1/2}\hbox{Prob}\{\max g_i>\beta(\log n)^{1/2}\}>(1-\frac{1}{e})\beta(\log n)^{1/2}$$