# expected value of squared infinity norm of vector of iid gaussians

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. 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.

• what is $\Phi$? the CDF of a $\mathcal N(0, 1)$? And $k$? Should it be $n$? Nov 5 '19 at 9:41
• yes, and yes, I will add that, thank you. Nov 5 '19 at 9:45
• By the way, the equality you give is only valid for $x_i \sim \mathcal N(0, 1)$, not for $x_i \sim \mathcal N(0, \sigma^2)$ as you claim. You can do some math and get an equality for $\mathcal N(0, \sigma^2)$ or restate the question. Nov 5 '19 at 9:51
• edited thank you. Nov 5 '19 at 9:52
• Here is the exact formula: $$\mathsf{E}\|X\|_{\infty}^2=2\sigma^2\int_0^{\infty}x(1-(2\Phi(x)-1)^n)\,dx.$$ Nov 6 '19 at 22:04

Let $$M_n:=\max_{1\le i\le n}|X_i|$$. Assume w.l.o.g. that $$\sigma=1$$. Then, using Markov's inequality ($$n\ge 2$$), for any $$c>0$$, \begin{align} \mathsf{E}M_n^2&\ge c\ln n\times\mathsf{P}(M_n\ge \sqrt{c\ln n}) \\[0.5em] &=c\ln n\times (1-[\mathsf{P}(|X_1|<\sqrt{c\ln n})]^n). \end{align}
Using the bound on the error function: $$\operatorname{erf}(x)\le \sqrt{1-\exp(-4x^2/\pi)}$$, one gets \begin{align} \mathsf{P}(|X_1|< \sqrt{c\ln n})&=\operatorname{erf}\left(\sqrt{c\ln(n)/2}\right) \\ &\le \sqrt{1-\exp(-2c\ln(n)/\pi)} \\ &=\sqrt{1-n^{-2c/\pi}}. \end{align}
Thus, for $$c\in (0,\pi/2)$$, $$\mathsf{E}M_n^2\ge c\ln n\times\left(1-\left(1-n^{-2c/\pi}\right)^{n/2}\right)=c\ln n\times(1-o(1)).$$