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

Given a random vector

$$$$x=(x_1, \ldots, x_n)$$$$

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

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

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

$$$$E(\|x||_\infty)=\int_0^\infty(1-(2\Phi(x)-1)^n)dx,$$$$

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.

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. 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, $$$$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}$$$$ 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, then $$0. 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 $$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$$.

• Can you add a few sentences about the structure of the argument here? It’s not easy to dive in to all the formulas. – Matt F. Nov 8 '19 at 18:38
• @MattF. : I am not sure what you mean. This whole argument is a straightforward calculation, consisting of 10 sentences, if I counted them correctly. If anything in particular is unclear or hard to comprehend, please let me know. – Iosif Pinelis Nov 8 '19 at 20:47
• I have added an explicit non-asymptotic lower bound on $E\|x\|_\infty^2$ which is asymptotically equivalent to $E\|x\|_\infty^2$ as $n\to\infty$. – Iosif Pinelis Nov 10 '19 at 2:40

It is known that the max of i.i.d. subgaussian random variables with variance $$\sigma^2$$ is on the order of $$\sigma \sqrt{\log n}$$ so you can expect the squared max of the random variables to be roughly $$\sigma^2 \log n$$. A reference for this result is 'High Dimensional Probability' by Vershynin. In this case, Jensen's inequality immediately gives you that $$\mathbf{E}[||x||_{\infty}^2] \ge (\mathbf{E}[||x||_{\infty}])^2 = \Omega(\sigma^2 \log n).$$

We can also show that this is the right order of magnitude. Consider an arbitrary $$\lambda > 0$$ ($$\lambda$$ will have to satisfy a condition that we will address later). Then

\begin{align*} \exp(\lambda \mathbf{E}(\max_i |x_i|)^2) &\le \mathbf{E}\exp(\lambda (\max_i |x_i|)^2) \\ &= \mathbf{E} \max_i \exp(\lambda |x_i|^2) \\ &\le \sum_{i=1}^n \mathbf{E}\exp(\lambda x_i^2). \end{align*} Now the last quantity is just the MGF of a chi-squared distribution which has an explicit form which is $$1/(\sqrt{1-2\lambda \sigma^2})$$. Then by taking the logs we have $$\mathbf{E}(\max_i |x_i|)^2 \le \frac{\log n}{\lambda} + \frac{1}{\lambda \sqrt{1-2\lambda \sigma^2}}.$$ Optimizing this quantity in $$\lambda$$, we let $$\lambda$$ be such that $$\lambda \sigma^2 = \frac{1}2 - \frac{1}{2 \log(n)^2}.$$ (Note in the conference of the MGF above, we needed $$\lambda \sigma^2 < 1/2$$ which is satisfied here). Then plugging back in, we see that $$\mathbf{E}(\max_i |x_i|)^2 \le \frac{4 \sigma^2 \log(n)}{1-1/\log(n)^2}$$ so $$\sigma^2 \log n$$ is the right order.

Here's a general way how to obtain lower bounds in this case. The infinity norm $$||\vec{X}||_\infty$$ is defined on $$\mathbb{R}^n$$ as

$$||\vec{X}||_\infty =\max(|X_1|, ..., |X_n|)$$

Consequently, we also have

$$||\vec{X}||_\infty^2 = \max(X_1^2, ..., X_n^2)$$

as $$X_i \leq X_j \implies X_i^2 \leq X_j^2$$. Now, the maximum of several i.i.d variables, also known as the largest order statistic, has the distribution

$$\max(X_1^2, ..., X_n^2) \sim \frac{d}{dx} F(x)^{n} = n \left(F(x)\right)^{n-1} f(x)$$

where $$f(x)$$ is the distribution of $$X_i^2$$ and $$F(x)$$ is its CDF. Finally, we therefore have

$$\mathbb{E}[||\vec{X}||_\infty^2] = n \int_{-\infty}^{\infty} x F(x)^{n-1} f(x) \ dx = \int_{-\infty}^{\infty} x \frac{d}{dx} F(x)^{n} \ dx$$

Use the substitution $$u = F(x)$$, and we obtain

$$\mathbb{E}[||\vec{X}||_\infty^2] = n \int_0^1 F^{-1}(u) u^{n-1} du$$

Now, for the random variables $$X_i^2$$ specifically, we have

$$f(x) = \frac{1}{\sqrt{2 \pi x}\ \sigma} e^{- \frac{x}{2 \sigma^2}} \theta(x), \;\;\; F(x) = \text{erf}\left(\frac{\sqrt{x}}{\sqrt{2} \sigma}\right)$$

and therefore

$$F^{-1}(u) = 2 \sigma^2 \text{erf}^{-1}(u)^2$$ .

Now, remarkably in this case, the function $$\text{erf}^{-1}(u)$$ has a Taylor series around $$u = 0$$ where all of the coefficients are positive. This means that any truncation of the series is strictly less than $$\text{erf}^{-1}(u)$$.

The first few terms are

$$\text{erf}^{-1}(u) = \frac{\sqrt{\pi}}{2} u + \frac{\pi^{\frac{3}{2}}}{24} u^3 + O(u^5)$$

Therefore, if you replace $$\text{erf}^{-1}(u)$$ with the truncated series in the expression for $$F^{-1}(u)$$ and integrate the resulting polynomial expression, you obtain a lower bound.

As an example, take the lowest order term in the above expansion. We then must have

$$\mathbb{E}[||\vec{X}||_\infty^2] \geq n \int_0^1 \sigma^2 \frac{\pi}{2} u^{n+1} du = \sigma^2 \frac{\pi}{2} \frac{n}{n+2}$$

As you take more terms in the Taylor expansion and evaluate the integral, you will obtain increasingly tighter lower bounds.

• Each of your lower bounds will be asymptotically constant for large $n$, whereas the correct asymptotics is $\sim2\sigma^2\ln n$. – Iosif Pinelis Nov 8 '19 at 17:16
• @IosifPinelis That's right for a fixed number of terms. If you want to reproduce the asymptotics, I suspect you'd also have to make the number of terms you include in the approximation a function of $n$. Admittedly, I wouldn't know how to connect this up at this point, and I'm also unsure which provides a better bound for various regions of the value of $n$. – bursneh Nov 8 '19 at 19:15
• Ah, as it happens, the Taylor series approach misses the fact that $\text{erf}^{-1}(u)$ has a logarithmic singularity at $u = 1$. This is likely the source of the logarithmic dependence on $n$. I'll edit the answer to include that when I have more time. – bursneh Nov 8 '19 at 20:30