Expected value of maximum and minimum of $n$ normal random variables

Let $X_1, \dots, X_n \sim N(\mu,\sigma)$ be normal random variables. Find the expected value of random variables $\max_i(X_i)$ and $\min_i(X_i)$.

The sad truth is I don't have any good idea how to start and I'll be glad for a hint.

As Robert Israel says, you only need to consider standard $N(0,1)$s. If $E_n$ is the expected value of the maximum of $n$ independent $N(0,1)$s, then the expected value of $\max_i(X_i)$ is $\mu+\sigma E_n$ and the expected value of $\min_i(X_i)$ is $\mu-\sigma E_n$.

Actually this is quite a cute problem, because there is a closed form up to $n=5$ given by $E_1=0$, $E_2=\pi^{-1/2}$, $E_3=(3/2)\pi^{-1/2}$, $E_4=3\pi^{-3/2}\cos^{-1}(-1/3)$, $E_5=(5/2)\pi^{-3/2}\cos^{-1}(-23/27)$.

But I don't think you will get a neat closed form for general $n$. Depending on your application, maybe an approximation formula would be useful, or maybe a computer program would be good. The first approximation formula you might use is $E_n\sim\sqrt{2\log(n)}$, but there are more accurate (and elaborate) ones if that is what you need (in which case, please say so).

To show the first five values of $E_n$ are as above, let $\phi(x)=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}$ be the standard normal density and $\Phi(x)$ the standard cdf. Then \begin{equation}\begin{split} E_n&=\int_{-\infty}^\infty x\dfrac{d}{dx}\Phi(x)^ndx\\ &=n\int_{-\infty}^\infty x\phi(x)\Phi(x)^{n-1}dx\\ &=n(n-1)\int_{-\infty}^\infty \phi(x)^2\Phi(x)^{n-2}dx\quad\text{(by parts)}\\ &=n(n-1)\int_{-\infty}^\infty \phi(x)^2\left(A(x)+\tfrac12\right)^{n-2}dx\quad\text{(where $A(x)=\Phi(x)-\tfrac12$),}\\ &=\frac{n(n-1)}{2\pi}\sum_{r=0}^{[n/2]-1}(\tfrac12)^{n-2-2r}\binom{n-2}{2r}\int_{-\infty}^\infty e^{-x^2}A(x)^{2r}dx\quad\text{(using antisymmetry of $A(x)$)}. \end{split}\end{equation}

So the $E_n$ come in pairs, and $E_{2n}$ and $E_{2n+1}$ can be written in terms of $\int_{-\infty}^\infty e^{-x^2}A(x)^{2r}dx$ for $r=0, \ldots, n-1$. We can get a closed form for this integral for $r=0$ and also, slightly surprisingly, for $r=1$, giving $E_1, \ldots, E_5$ above.

The only way I know how to do this is by introducing $$I_n(s)=\int_{-\infty}^\infty e^{-sx^2/2}A(x)^{2n}dx.$$ Then $I_n(s)$ satisfies a strange reduction rule $$I_{n+1}(s)=\frac{2n+1}{2\pi\sqrt{s}}\int_0^{1/\sqrt{s}}\left(1+y^2\right)^{-1}I_{n}\left(1+s(1+y^2)\right)dy.$$ As a consequence, \begin{equation}\begin{split} I_0(s)&=\sqrt\frac{2\pi}{s},\\ I_1(s)&=\frac{1}{\sqrt{2\pi s}}\tan^{-1}\left(\frac{1}{\sqrt{s(s+2)}}\right),\\ %I_2(s)&=3(2\pi)^{-3/2}s^{-1/2}\int_0^{s^{-1/2}}\left(1+y^2\right)^{-1}\left(3+2y^2\right)^{-1/2}\tan^{-1}\left(\left((3+2y^2)(5+2y^2)\right)^{-1/2}\right)dy \end{split}\end{equation} and the above formulae for $E_1, \ldots, E_5$ follow from the values of $I_0(2)$ and $I_1(2)$, using standard trig equivalences.

To prove the reduction rule, \begin{equation}\begin{split} \int_0^{1/\sqrt{s}}\left(1+y^2\right)^{-1}&I_{n}\left(1+s(1+y^2)\right)dy\\ &=\int_0^{1/\sqrt{s}}\int_{-\infty}^\infty\left(1+y^2\right)^{-1}e^{-(1+s(1+y^2))x^2/2}A(x)^{2n}dxdy\\ &=\int_0^{1/\sqrt{s}}\int_{-\infty}^\infty\left(1+y^2\right)^{-1}e^{-s(1+y^2)x^2/2}\sqrt{2\pi}\phi(x)A(x)^{2n}dxdy\\ &=\int_0^{1/\sqrt{s}}\int_{-\infty}^\infty\left(1+y^2\right)^{-1}e^{-s(1+y^2)x^2/2}\frac{\sqrt{2\pi}}{2n+1}\dfrac{d}{dx}A(x)^{2n+1}dxdy\\ &=s\frac{\sqrt{2\pi}}{2n+1}\int_0^{1/\sqrt{s}}\int_{-\infty}^\infty xe^{-s(1+y^2)x^2/2}A(x)^{2n+1}dxdy\quad\text{(by parts in $x$)}\\ &=s\frac{\sqrt{2\pi}}{2n+1}\int_{-\infty}^\infty xe^{-sx^2/2}A(x)^{2n+1}\left(\int_0^{1/\sqrt{s}} e^{-sy^2x^2/2}dy\right)dx\\ &=s\frac{\sqrt{2\pi}}{2n+1}\int_{-\infty}^\infty xe^{-sx^2/2}A(x)^{2n+1}\left(\int_0^x \frac{e^{-y^2/2}}{\sqrt{s}x}dy\right)dx\\ &=\sqrt{s}\frac{2\pi}{2n+1}\int_{-\infty}^\infty e^{-sx^2/2}A(x)^{2n+2}dx\\ &=\sqrt{s}\frac{2\pi}{2n+1}I_{n+1}(s). \end{split}\end{equation}

Presumably the $X_i$ are independent. If $\Phi$ is the standard normal cdf, $$P(\max_i X_i < \mu + t \sigma) = \prod_i P(X_i < \mu + t \sigma) = \Phi(t)^n$$ so $$ E[\max_i X_i] = \mu + \sigma \int_{-\infty}^\infty t \dfrac{d}{dt} \Phi(t)^n\ dt $$ Maple tells me that for $n=2$ the integral is $1/\sqrt{\pi}$, and for $n=3$ it is $3/(2\sqrt{\pi})$. It doesn't know of closed forms for $n > 3$, and neither do I. The numerical values for $n=2$ to $10$ are $\matrix{.56418958354775628695,& .84628437532163443042,& 1.0293753730039641321,\cr 1.1629644736405196128,& 1.2672063606114712976,& 1.3521783756069043992,\cr 1.4236003060452777531,& 1.4850131622092370063,& 1.5387527308351728560\cr}$