Given a random vector 


\begin{equation}
x=(x\_1, \ldots, x\_n)
\end{equation}


with independent and identically distributed entries $x\_i \sim \mathcal{N}(0,\sigma^2)$, I would like to find a lower bound $f(n)$ 


\begin{equation}
\mathbb{E}[||x||^2\_{\infty}] \geq f(n)
\end{equation}


which is reasonably tight. I know that the following equality for the non squared norm holds when $\sigma^2 =1$: 


\begin{equation}
E(\|x||\_\infty)=\int\_0^\infty(1-(2\Phi(x)-1)^n)dx, 
\end{equation}


where $\Phi$ is the CDF of $\mathcal{N}(0,1)$, see the comment to this question by @Did [here](https://math.stackexchange.com/questions/1456666/probability-distribution-of-infinity-norm-of-a-vector-of-independent-random-vari). Unfortunately I am not even sure on how to (tightly) lower bound the right integral for this special case. 


Any help on solving the general case is much appreciated. 



expected value of squared infinity norm of vector of iid gaussians
Let $Z\_i:=x\_i$ and $M:=M\_n:=\|x\|\_\infty=\max\_1^n|Z\_i|$. 
By rescaling, without loss of generality $\sigma=1$. So, for real $u>0$
\begin{multline}
 P(M^2>u)=P(M>\sqrt u)=1-P(\max\_1^n|Z\_i|\le\sqrt u)=1-P(|Z\_1|\le\sqrt u)^n \\ 
=1-(1-2G(\sqrt u))^n=1-e^{-ng(u)}, \tag{1}
\end{multline}
where 
$$G(x):=P(Z\_1>x)\sim\frac1{x\sqrt{2\pi}}e^{-x^2/2}
$$
as $x\to\infty$ and 
$$g(u):=-\ln(1-2G(\sqrt u))\sim2G(\sqrt u)\sim\frac2{\sqrt{2\pi u}}e^{-u/2}
=e^{-u/(2+o(1))}
$$
as $u\to\infty$. 


Also, $g(u)$ decreases from $\infty$ to $0$ as $u$ increases from $0$ to $\infty$. So, for each natural $n\ge3$ there are unique positive real numbers $u\_n$ and $v\_n$ such that 
$$ng(u\_n)=\ln n,\quad ng(v\_n)=1. 
$$
Clearly, $0<u\_n<v\_n<\infty$. Also, 
$$\frac{\ln n}n=g(u\_n)=e^{-u\_n/(2+o(1))}\quad\text{and}\quad
\frac{\ln n}n=e^{-(1+o(1))\ln n},
$$
whence 
$$u\_n\sim2\ln n\quad\text{and, similarly,}\quad v\_n\sim2\ln n. 
$$


Next,
\begin{equation}
 EM^2=\int\_0^\infty P(M^2>u)\,du=\int\_0^\infty (1-e^{-ng(u)})\,du=I\_1+I\_2+I\_3, \tag{2}
\end{equation}
where 
$$I\_1:=\int\_0^{u\_n}(1-e^{-ng(u)})\,du,\quad I\_2:=\int\_{u\_n}^{v\_n}(1-e^{-ng(u)})\,du,\quad I\_3:=\int\_{v\_n}^\infty (1-e^{-ng(u)})\,du. 
$$
If $0<u<u\_n$, then $0<e^{-ng(u)}<e^{-ng(u\_n)}=1/n$. So, 
$$I\_1\sim u\_n.$$
Next,
$$I\_2\le v\_n-u\_n=o(u\_n), 
$$
$$I\_3<\int\_{v\_n}^\infty ng(u)\,du\sim
\int\_{v\_n}^\infty n\frac2{\sqrt{2\pi u}}e^{-u/2}\,du
\sim 2n\frac2{\sqrt{2\pi v\_n}}e^{-v\_n/2}
\sim 2ng(v\_n)=2=o(u\_n). 
$$
We conclude that, for $\sigma=1$,
$$E\|x\|\_\infty^2=EM^2\sim u\_n\sim2\ln n.
$$
So, for any real $\sigma>0$,
$$E\|x\|\_\infty^2\sim2\sigma^2\ln n.
$$




---


Along the same lines, one can give an explicit non-asymptotic lower bound on $E\|x\|\_\infty^2$ which will be asymptotically equivalent to $E\|x\|\_\infty^2$ as $n\to\infty$. Indeed, one can use the inequality 
$$G(t)\ge B(t):=\frac{f(t)}{\sqrt{t^2+2}}
$$
for real $t\ge0$, where $f$ is the standard normal pdf, so that $f(t)=\frac1{\sqrt{2\pi}}\,e^{-t^2/2}$ for real $t$. The latter lower bound on $G(t)$ is a simpler, even if a bit less accurate, version of [Birnbaum's lower bound](https://projecteuclid.org/euclid.aoms/1177731611) $B\_1(t):=f(t)(\sqrt{t^2+4}-t)/2$ on $G(t)$; we have $B\_1(t)>B(t)$ for all real $t\ge0$. 
So, assuming that $\sigma=1$ and $n\ge16$, letting 
\begin{equation\*}
 w\_n:=2\ln n-2\ln\ln n, 
\end{equation\*}
and recalling (1), for $u\in[0,w\_n]$ we have $\ln\ln n>1$ and 
\begin{align\*}
 P(M^2>u)&=1-(1-2G(\sqrt u))^n \\ 
 &\ge1-\exp\big\{-2nG(\sqrt u)\big\} \\ 
 &\ge1-\exp\big\{-2nG(\sqrt w\_n)\big\} \\ 
 &\ge1-\exp\Big\{-2n\frac{f(\sqrt w\_n)}{\sqrt{w\_n+2}}\Big\} \\ 
 &=1-\exp\Big\{-\frac1{\sqrt\pi}\frac{\ln n}{\sqrt{1+\ln n-\ln\ln n}}\Big\} \\ 
 &\ge1-\delta\_n, 
\end{align\*}
where
\begin{equation\*}
 \delta\_n:=\exp\Big\{-\sqrt{\frac{\ln n}\pi}\,\Big\}\to0. 
\end{equation\*}
Now it follows from (2) that, for $\sigma=1$, 
\begin{equation\*}
 E\|x\|\_\infty^2=EM^2\ge\int\_0^{w\_n} P(M^2>u)\,du
 \ge(1-\delta\_n)w\_n=(1-\delta\_n)(1-\epsilon\_n)2\ln n,
\end{equation\*}
where 
\begin{equation\*}
 \epsilon\_n:=\frac{\ln\ln n}{\ln n}\to0. 
\end{equation\*}
So, for any real $\sigma>0$ and any $n\ge16$,
$$E\|x\|\_\infty^2\ge2(1-\delta\_n)(1-\epsilon\_n)\sigma^2\ln n\sim2\sigma^2\ln n,
$$
as claimed. 


For $n=1,\dots,15$, the values of $E\|x\|\_\infty^2$ can be easily computed numerically, using (2) and (1), with any degree of accuracy, say to get these $15$ approximate values for $E\|x\|\_\infty^2/\sigma^2$: $1, 1.63662, 2.10266, 2.47021, 2.77375, 3.03236, 3.25771, 3.45743, 
3.6368, 3.79962, 3.9487, 4.08621, 4.21382, 4.33288, 4.44447$. 


