4
$\begingroup$

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 \begin{equation} \text{ argmax}_{i=1,\ldots,(n^2+n)/2} |X_i| \leq n \end{equation}

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – dandide Dec 2 at 17:36
3
$\begingroup$

$\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^-$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.