Lower bound on the probability that the maximum of a sequence of $n$ i.i.d. standard normal r.v.'s exceeds $x$

Question

Let $X_{\max}=\max(X_1,X_2,\ldots,X_n)$ where $n$ is large and each $X_i$ is i.i.d. standard normal random variable, i.e. $X_i\sim\mathcal{N}(0,1)$. Is there a lower bound on the probability $P(X_{\max}\geq x)$ using elementary functions in terms of $n$ and constant $x$ independent of $n$?

My guess is that there is a lower bound is in the form $P(X_{\max}\geq x)\geq e^{-x/\sqrt{\log n}}$, however, I am wondering if that is true, and, if it is, how to prove it. I am pretty new to the extreme value theory, and would appreciate any help.

Answer 1

$$ \Pr(\max>x) = 1-\Pr(\max\le x) = 1-\Pr(\text{for }i=1,\ldots, n,\quad X_i\le x) $$ $$ = 1-\Big(\Pr(X_1\le x)\Big)^n = 1 - \Big(\Phi(x)\Big)^n. $$

If you mean a computationally efficient lower bound, it might make sense to ask about computationally efficient upper bounds on $\Phi(x)$. Things like that are known.

Answer 2

\begin{align} \mathtt{P}(X_{max} \geq x) & = 1 - \mathtt{P}(X_1 \leq x,\,\ldots,\,X_n \leq x) \\ & = 1-[\mathtt{P}(X \leq x)]^n. \end{align} where $X$ is a standard $\mathcal{N}(0,1)$ normal random variable.

Now note that \begin{align} P(X \leq x) = \frac{1}{2}\left[1 + \mathrm{erf}\left(\frac{x}{\sqrt{2}}\right)\right] \end{align}

We also have the special function \begin{align} \mathrm{Q}(x) = \frac{1}{2}\left(1-\mathrm{erf}\left(\frac{x}{\sqrt{2}}\right)\right). \end{align} It can be shown that there are $x$-independent constants $C,D$ such that (See http://arxiv.org/pdf/1202.6483v2.pdf) \begin{align} \mathrm{Q}(x) \geq Ce^{-D x^2} \end{align} In particular, \begin{align} \frac{1}{2}\left(1-\mathrm{erf}\left(\frac{x}{\sqrt{2}}\right)\right) \geq Ce^{-Dx^2} \end{align} and therefore \begin{align} \mathrm{erf}\left(\frac{x}{\sqrt{2}}\right) \leq 1-2Ce^{-Dx^2} \end{align}

As a result, we obtain \begin{align} P(X \leq x) \leq \frac{1}{2}\left[2 -2Ce^{-Dx^2}\right] = 1-Ce^{-Dx^2/2} \end{align} Finally, \begin{align} \mathtt{P}(X_{max} \geq x) & = 1-[\mathtt{P}(X \leq x)]^n \\ & \geq 1-[1-Ce^{-Dx^2/2}]^n \end{align} It is also easy to show using the standard Chernoffupper bound on the Q function that \begin{align} \mathtt{P}(X_{max} \geq x) & \leq 1-[1-e^{-x^2/2}]^n \end{align} So the upper and lower bounds have the same asymptotic behavior with respect to $n$.