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.

  • $\begingroup$ what is $\Phi$? the CDF of a $\mathcal N(0, 1)$? And $k$? Should it be $n$? $\endgroup$
    – G. Gare
    Nov 5 '19 at 9:41
  • $\begingroup$ yes, and yes, I will add that, thank you. $\endgroup$
    – sigmatau
    Nov 5 '19 at 9:45
  • $\begingroup$ 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. $\endgroup$
    – G. Gare
    Nov 5 '19 at 9:51
  • $\begingroup$ edited thank you. $\endgroup$
    – sigmatau
    Nov 5 '19 at 9:52
  • 1
    $\begingroup$ Here is the exact formula: $$ \mathsf{E}\|X\|_{\infty}^2=2\sigma^2\int_0^{\infty}x(1-(2\Phi(x)-1)^n)\,dx. $$ $\endgroup$
    – d.k.o.
    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)). $$


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.