# Probability of achieving the maximum among absolute value of Gaussians

Yesterday the following question was asked by user sigmatau:

I'm interested in the following question:

given $$n$$ i.i.d. random variables $$X_i \sim \mathcal{N}(0,\sigma^2_1), i=1,\ldots,n$$ and $$n(n-1)/2$$ i.i.d. random variables (independent w.r.t. the first set of random variables) with $$X_{n+j} \sim \mathcal{N}(0, \sigma^2_2), j = 1, \ldots, n(n-1)/2$$, what is the probability that $$$$\text{ argmax}_{i=1,\ldots,(n^2+n)/2} |X_i| \leq n$$$$

In particular I'm interested in the case where $$\sigma^2_1=2, \sigma^2_2=1$$. In this case some simple numerical simulations suggest that the event that I want to know the probability of happens with high probability, but I was not able to give a closed form estimate of it. Any help is much appreciated.

The question was deleted soon afterwards by the user. I think the question might be of interest to some other users and am therefore recreating it here, accompanied with an answer.

• it was asked again at math.stack and is added to question that the event can be written as $\bigcup \limits_{t \in \mathbb{R}} \{ Z_0 > t \} \cap \{Z_1 = t\}$ but I fail to see why it goes over $t$, I gave a wrong answer and I lack the knowledge to understand yours fully but is nice to see it solved – dandide Dec 2 at 17:36

$$\newcommand{\si}{\sigma}$$ Let $$M_n$$ be the maximum of $$n$$ iid standard normal random variables (r.v.'s) $$Z_1,\dots,Z_n$$, and let $$L_N$$ be the maximum of $$N$$ iid standard normal r.v.'s $$W_1,\dots,W_N$$, where $$N:=n(n-1)/2$$. Assume also the r.v.'s $$M_n$$ and $$L_N$$ are independent. By rescaling, the question can be restated as follows:

Given a positive real $$\si$$, how does the probability $$P(M_n>\si L_N)$$ behave?

The answer to this questions is this:

$$P(M_n>\si L_N)\longrightarrow \begin{cases} 1&\text{ if }\si<1/\sqrt2, \\ 0&\text{ if }\si\ge1/\sqrt2; \end{cases} \tag{1}$$ the convergence everywhere here is as $$n\to\infty$$. Moreover, it does not matter that the r.v.'s $$M_n$$ and $$L_N$$ are independent.

Indeed, it is a well-known fact of the so-called extreme value theory (see e.g. Theorem 18.4) that $$M_n=d_n+\frac{G_n}{\sqrt{2\ln n}}, \tag{2}$$ where $$d_n:=\sqrt{2\ln n}-\frac{\ln\ln n+\ln(4\pi)}{2\sqrt{2\ln n}}$$ and $$G_n\to G$$ in distribution, where in turn $$G$$ is a Gumbel r.v.

So, $$M_n\sim d_n\sim\sqrt{2\ln n}$$ and $$L_N\sim d_N\sim\sqrt{2\ln N}\sim\sqrt{4\ln n}$$ in probability, which immediately implies (1) for $$\si\ne1/\sqrt2$$.

The case $$\si=1/\sqrt2$$ (which was of special interest in the original question), a bit more effort shows that $$\frac1{\sqrt2}\,d(N)-d(n)\sim\frac{\ln\ln n}{4\sqrt{2\ln n}} >>\frac1{\sqrt{\ln n}},$$ where $$A>>B$$ means $$B=o(A)$$. Now, in view of (2), the case $$\si=1/\sqrt2$$ follows as well.

Somehow, I have just noticed that the original question was, not about the maximum of $$n$$ iid standard normal r.v.'s, but about the maximum of the absolute values of $$n$$ iid standard normal r.v.'s. Anyway, (1) holds as well with $$M_n^{|\;|}:=\max_1^n|Z_i|$$ and $$L_N^{|\;|}:=\max_1^N|W_j|$$ in place of $$M_n=\max_1^n Z_i$$ and $$L_N=\max_1^N W_j$$, respectively. Here one only needs to make small adjustments. Indeed, the essential fact used in the above derivation is that $$M_n=d_n+\frac{\ln\ln n}{\sqrt{\ln n}}\,o_P(1), \tag{3}$$ where $$o_P(1)$$ stands for a r.v. depending on $$n$$ and converging to $$0$$ in probability. But (3) holds with $$M_n^-:=\max_1^n(-Z_i)$$ in place of $$M_n$$, because $$M_n^-$$ equals $$M_n$$ in distribution. So, (3) holds with $$M_n^{|\;|}$$ in place of $$M_n$$, because every value of $$M_n^{|\;|}$$ is either the corresponding value of $$M_n$$ or the corresponding value of $$M_n^-$$.