7
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you add a few sentences about the structure of the argument here? It’s not easy to dive in to all the formulas. $\endgroup$ – Matt F. Nov 8 at 18:38
  • $\begingroup$ @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. $\endgroup$ – Iosif Pinelis Nov 8 at 20:47
  • $\begingroup$ 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$. $\endgroup$ – Iosif Pinelis Nov 10 at 2:40
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Each of your lower bounds will be asymptotically constant for large $n$, whereas the correct asymptotics is $\sim2\sigma^2\ln n$. $\endgroup$ – Iosif Pinelis Nov 8 at 17:16
  • $\begingroup$ @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$. $\endgroup$ – bursneh Nov 8 at 19:15
  • $\begingroup$ 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. $\endgroup$ – bursneh Nov 8 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.