Expectation of the maximum of gaussian random variables

The $\max$-central limit theorem (Fisher-Tippet-Gnedenko theorem) can be used to provide a decent approximation when $n$ is large. See this example at reference page for extreme value distribution in Mathematica.

The $\max$-central limit theorem states that $F_\max(x) = \left(\Phi(x)\right)^n \approx F_{\text{EV}}\left(\frac{x-\mu_n}{\sigma_n}\right)$, where $F_{EV} = \exp(-\exp(-x))$ is the cumulative distribution function for the extreme value distribution, and $$ \mu_n = \Phi^{-1}\left(1-\frac{1}{n} \right) \qquad \qquad \sigma_n = \Phi^{-1}\left(1-\frac{1}{n} \cdot \mathrm{e}^{-1}\right)- \Phi^{-1}\left(1-\frac{1}{n} \right) $$ Here $\Phi^{-1}(q)$ denotes the inverse cdf of the standard normal distribution.

The mean of the maximum of the size $n$ normal sample, for large $n$, is well approximated by $$ \begin{eqnarray} m_n &=& \sqrt{2} \left((\gamma -1) \Phi^{-1}\left(2-\frac{2}{n}\right)-\gamma \Phi^{-1}\left(2-\frac{2}{e n}\right)\right) \\ &=& \sqrt{\log \left(\frac{n^2}{2 \pi \log \left(\frac{n^2}{2\pi} \right)}\right)} \cdot \left(1 + \frac{\gamma}{\log (n)} + \mathcal{o} \left(\frac{1}{\log (n)} \right) \right) \end{eqnarray}$$ where $\gamma$ is the Euler-Mascheroni constant.

Here is a good asymptotics for this:

Let $f(x)=\frac{e^{-x^2/2}}{\sqrt{2\pi}}$ be the density and $\Phi(x)=\int_{-\infty}^x f(u)du$ be the CDF of the standard normal random variable $X$. Let $Z=Z(n)=\max(X_1,\dots,X_n)$ where $X_i$ are i.i.d.\ normal ${\cal N}(0,1)$. We are interested in $\mathbb{E}Z(n)$.

Since the CDF of $Z$ is given by $F_Z(z)=\mathbb{P}(Z\le z)=\mathbb{P}(X_1\le z,\dots,X_n\le z)=\mathbb{P}(X\le z)^n=\Phi(z)^n$, hence its density is $\frac{d}{dz}\left[\Phi(z)^n\right]=n f(z)\Phi(z)^{n-1}$ and \begin{align*} \mathbb{E}Z(n)&=\int_{-\infty}^\infty z\cdot n f(z)\Phi(z)^{n-1} dz =\int_{-\infty}^0 z\cdot \frac{d}{dz}\left[\Phi(z)^n\right] dz -\int_0^{\infty} z\cdot \frac{d}{dz}\left[1-\Phi(z)^n\right] dz \\ &=-\int_{-\infty}^0 \Phi(z)^n dz +\int_0^{\infty} 1-\Phi(z)^n dz \end{align*} using the integration parts and noting that $\lim_{z\to-\infty}z\cdot \Phi(z)^n=0$ and $ \lim_{z\to\infty}z\cdot \left[1-\Phi(z)^n\right]=0$ by e.g.\ L'Hôpital's rule. Next, \begin{align*} 0\le \int_{-\infty}^0 \Phi(z)^n dz \le \int_{-\infty}^{-1} e^{zn} dz +\int_{-1}^{0} \Phi(0)^n dz = \frac{1}{n}e^{-n} + 2^{-n}\to 0 \end{align*} since $f(z)<e^z$ (and hence $\Phi(z)<e^{z}$ too) for $x\le -1$, and $\Phi(z)\le \Phi(0)=1/2$ for $z\le 0$.

Now it only remains to estimate $\int_0^{\infty} 1-\Phi(z)^n dz$. Observe that $$ \frac{1-\Phi(z)}{f(z)/z}\to 1\text{ as }z\to+\infty. $$ since for $z> 0$ \begin{align*} 1-\Phi(z)&=\int_z^\infty \frac{e^{-x^2/2}}{\sqrt{2\pi}}dx \le\int_z^\infty \frac{x}{z} \cdot \frac{ e^{-x^2/2}}{\sqrt{2\pi}}dx =\frac 1z\cdot \frac{ e^{-z^2/2}}{\sqrt{2\pi}}; \\ 1-\Phi(z) &\ge \int_z^{z+1} \frac{e^{-x^2/2}}{\sqrt{2\pi}}dx \ge \int_z^{z+1} \frac{x}{z+1} \cdot \frac{ e^{-x^2/2}}{\sqrt{2\pi}}dx = \frac {1-e^{-1/2-z}}{1+1/z}\cdot \frac{ e^{-z^2/2}}{z\sqrt{2\pi}}, \end{align*} so we can write $$ 1-\Phi(z)=c_z\frac{ e^{-z^2/2}}{z\sqrt{2\pi}}\quad\text{for }z>0 $$ where $c_z\to 1$ as $z\to +\infty$.

Let $y=y(n)=\sqrt{2\ln n}$. For $z\ge y$ we have %$1-\Phi(z)\ll \frac 1n$, \begin{align*} \int_{y}^{\infty} 1-\Phi(z)^n dz&= \int_{y}^{\infty} 1-\left[1- c_z\frac{ e^{-z^2/2}}{z\sqrt{2\pi}}\right]^n dz \le \int_{y}^{\infty} n c_z\frac{ e^{-z^2/2}}{z\sqrt{2\pi}} dz \\ &\le \int_{y}^{\infty} n c_z \frac{z}{y^2} \frac{e^{-z^2/2}}{\sqrt{2\pi}} dz \le \frac{n\max_{z\ge y} c_z}{y^2\sqrt{2\pi}} \int_{y}^{\infty} z e^{-z^2/2} dz =O\left(\frac1{\ln n}\right). \end{align*}

Let us estimate now $\int_{0}^{y} \Phi(z)^n dz$. Fix $\varepsilon>0$ small, and note that if $1\le z\le y-\varepsilon$ then $$ 1-\Phi(z)\ge \left(\min_{1\le z\le y} c_z\right) \frac{n^{-1}\, e^{\varepsilon y-\frac{\varepsilon^2}2}}{(y-\varepsilon)\sqrt{2\pi}} = \frac 1n\, \frac{c_1}{1-o(1)} \frac{e^{\varepsilon y}}{y}\gg \frac 1n $$ for some $c_1(\varepsilon)>0$ and where $o(1)\to 0$ as $n\to\infty$; note also that $e^{\varepsilon y}/y\to\infty $ as $y\to\infty$. This yields $\Phi(z)^n\le \exp\left(-(c_1+o(1))e^{\varepsilon y}/y\right)$. Hence \begin{align*} \int_0^{y-\varepsilon}\Phi(z)^n dz&\le \int_0^1 \Phi(1)^n dz+ \int_1^{y-\varepsilon} \Phi(z)^n dz \le 0.85^n+\int_1^{y-\varepsilon} \exp\left(-(c_1+o(1))e^{\varepsilon y}/y\right) dz \\ & \le 0.85^n+ y\exp\left(-(c_1+o(1))e^{\varepsilon y}/y\right) \to 0\qquad\text{ as }n,y\to\infty. \end{align*} Consequently, since $\int_{y-\varepsilon}^y \Phi(z)^n dz\le \varepsilon$, we conclude $$ \limsup_{n\to\infty} |\mathbb{E}Z(n)-y(n)|\le \varepsilon $$ Since $\varepsilon>0$ is arbitrary, this means $$ \mathbb{E}Z(n)=\sqrt{2\ln n}+o(1). $$

Here a simpler proof of the following result : Let $n\in \mathbb{N}^*$. $\mathbb{E}(\max_{1\leq i \leq n}Z_i) \underset{n\rightarrow \infty}{\sim} \sqrt{2\ln(n)}$ with $ Z_i$, i=1,...,n be i.i.d $\mathcal{N}(0,1)$. We are going to upper bound and lower bound the expectation.

Upper bound: Let $\lambda \in \mathbb{R}^+$. By Jensen's inequality, we get: $\exp(\lambda \mathbb{E}(\max_{1\leq i \leq n}Z_i))\leq\mathbb{E}(\exp(\lambda \max_{1\leq i \leq n}Z_i))\leq\mathbb{E}(\max_{1\leq i \leq n}\exp(\lambda Z_i)))\leq \sum_{i=1}^n\mathbb{E}(\exp(\lambda Z_i))=n\times \exp(\frac{\lambda^2}{2})$. Thus, $\mathbb{E}(\max_{1\leq i \leq n}Z_i)\leq \frac{\ln n}{\lambda}+\frac{\lambda}{2}$. By optimizing on $\lambda$, we obtain $\mathbb{E}(\max_{1\leq i \leq n}Z_i)\leq \sqrt{2\ln n}$.

Lower bound: To lower bound the expectation, a smart idea is to use that $|\mathbb{E}(X)-Med(X)|\leq Var(X)$ for all random variable $\mathbb L^2$. We note $M_n=Med(\max_{1\leq i \leq n}Z_i))$ and by Poincaré inequality, we can show that $Var(\max_{1\leq i \leq n}Z_i))\leq1$. Therefore, $\mathbb{E}(\max_{1\leq i \leq n}Z_i)\geq M_n-1$.

By the definition of the median, we have $\mathbb{P}(\max_{1\leq i \leq n}Z_i\leq M_n)=\frac{1}{2}$, so $\phi(M_n)=\frac{1}{2^\frac{1}{n}}$ with $\phi(x)=\mathbb{P}(X\leq x)$ where $X \sim \mathcal{N}(0,1)$. Finally, we use the fact that for all $x \in \mathbb{R^+}$, $Q(x)=1-\phi(x)\leq \frac{1}{2}\exp(-\frac{x^2}{2})$, then for $0< t\leq \frac{1}{2}$, $Q^{-1}(t)\geq\sqrt{2|\ln(2t)|}.$ Now, we have $Q(M_n)=1-\frac{1}{2^\frac{1}{n}}\leq \frac{\ln 2}{n}$. Thus, $M_n\geq Q^{-1}(\frac{\ln2}{n})\geq a_n :=\sqrt{2|\ln(2\frac{\ln(2)}{n})|}$.

$\textbf{Conclusion:}$ $\sqrt{2\ln n}\geq\mathbb{E}(\max_{1\leq i \leq n}Z_i)\geq M_n-1\geq a_n-1$. Hence, the desired result because $a_n\sim \sqrt{2\ln n}$.