Lower bound on the probability that the maximum of a sequence of $n$ i.i.d. standard normal r.v.'s exceeds $x$ 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.
 A: $$
\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.
A: \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$.
