# Prove that the maximum of $n$ independent standard normal random variables, is asymptotically equivalent to $\sqrt{2\log n}$ almost surely.

Lets $(X_n)_{n\in\mathbb{N}}$ be an iid sequence of standard normal random variables. Define $$M_n=\max_{1\leq i\leq n} X_i.$$ Prove that $$\lim_{n\rightarrow\infty} \frac{M_n}{\sqrt{2\log n}}=1\quad\text{a.s.}$$

I used the fact that $$\left(\frac{1}{x}-\frac{1}{x^3}\right)e^{-\frac{x^2}{2}}\leq\mathbb P(X_n>x)\leq \frac{1}{x}e^{-\frac{x^2}{2}},$$

and the Borel Cantelli lemmas to prove that $$\limsup_{n\rightarrow\infty} \frac{X_n}{\sqrt{2\log n}}=1\quad\text{a.s.}$$

I used Davide Giraudo's comment to show $$\limsup_n \frac{M_n}{\sqrt{2\log n}}=1\quad \text{a.s.}$$

I have no idea how to compute the $\liminf$. Borel-Cantelli give us tools to compute the $\limsup$ of sets, I am unsure of how to argue almost sure convergence. Any help would be appreciated.

## 2 Answers

Your estimate gives that for each positive $\varepsilon$, we have $$\sum_i\mathbb P(M_{2^{i}}>(1+\varepsilon)\sqrt 2\sqrt{i+1})<\infty$$ (we use the fact that $\mathbb P(M_n>x)\leqslant n\mathbb P(X_1\gt x)$).

We thus deduce that $\limsup_iM_{2^{i}}/(\sqrt{2(i+1)})\leqslant 1+\varepsilon$ almost surely. Taking $\varepsilon:=1/k$, we get $\limsup_iM_{2^{i}}/(\sqrt{2(i+1)})\leqslant 1$ almost surely. To conclude, notice that if $2^i\leqslant n\lt 2^{i+1}$, $$\frac{M_n}{\sqrt{2\log n}}\leqslant \frac{M_{2^{i+1}}}{\sqrt{2i}}.$$

For the $\liminf$, define for a fixed positive $\varepsilon$, $$A_n:=\left\{\frac{M_n}{\sqrt{2\log n}}\lt 1-\varepsilon\right\}.$$ A use of the estimate on the tail of the normal distribution show that the series $\sum_n \mathbb P(A_n)$ is convergent, hence by the Borel-Cantelli lemma, we have $\mathbb P\left(\limsup_n A_n\right)=0$. This means that for almost every $\omega$, we can find $N=N(\omega)$ such that if $n\geqslant N(\omega)$, then $$\frac{M_n(\omega)}{\sqrt{2\log n}}\geqslant 1-\varepsilon.$$ This implies that $$\liminf_{n\to \infty}\frac{M_n(\omega)}{\sqrt{2\log n}}\geqslant 1-\varepsilon \quad \mbox{a.e.}$$ Here again, taking $\varepsilon:=1/k$, we obtain that $$\liminf_{n\to \infty}\frac{M_n(\omega)}{\sqrt{2\log n}}\geqslant 1\quad \mbox{a.e.}$$

• So I am mainly having trouble with justifying the first sum converges. I get $$\mathbb{P}(M_{2^i}>\sqrt{(1+\epsilon)2(i+1)})=1-(1-\mathbb{P}(X_{2^i}>\sqrt{(1+\epsilon)2(i+1)}))^{2^i} \leq 1-(1-\frac{1}{\sqrt{(1+\epsilon)2(i+1)}}e^{-(1+\epsilon)(i+1)})^{2^i}$$ Oct 7 '14 at 10:15
• I edited. Is it clearer? Oct 7 '14 at 10:18
• yes significantly. Thank you. So that shows that $\limsup$ of $\frac{M_n}{\sqrt{2\log n}}\leq 1$, but not the $\liminf\geq1$. Oct 7 '14 at 10:27
• It may be not the case that $\liminf\geq 1$, however the limsup is greater than $1$ because $M_n\geq X_n$. Oct 7 '14 at 11:10
• Sorry, I missed the fact that you have a limit and not only a limsup. Oct 7 '14 at 11:22

Not an answer, but a related comment that is too long for a comment box ...

This question made me curious to compare:

• the pdf of the sample maximum (given a sample of size $$n$$ drawn on a N(0,1) parent), say $$f(x;n):$$

$$f(x) = \frac{2^{\frac{1}{2}-n} n e^{-\frac{x^2}{2}} \left(1+\text{erf}\left(\frac{x}{\sqrt{2}}\right)\right)^{n-1}}{\sqrt{\pi }}$$ where erf(.) denotes the error function, to

• the asymptote proposed by the question $$\sqrt{2 \log n}$$

... when $$n$$ is very large (say $$n$$ = 1 million).

The diagram compares:

The distribution does not, in fact, converge to the asymptote in any meaningful manner, even when $$n$$ is very large, such as $$n$$ = 1 million or 100 million or even a billion.

• Are you using the right logarithm? (I.e. base $e$ and not base 10?) Oct 1 '18 at 0:13
• Yes - $\sqrt{2 \log \left(10^6\right)}$ = 5.25 ... as shown in the diagram above (the red line). By contrast, with base 10, the same calculation would be equal to $2 \sqrt{3}$ which is approx 3.46. Oct 1 '18 at 7:17
• Using the large-$x$ asymptotics of the error function, I found that the maximum is attended at $\sqrt {2\log n} \left( {1 + \mathcal{O}\left( {\frac{1}{{\log n}}} \right)} \right)$, showing that the convergence is very slow.
– Gary
Nov 5 '20 at 10:47