Let $\{X_i\}_{i=1}^n$ be an i.i.d. sequence of $\mathcal{N}(0, \sigma^2)$ variables, and consider the random variable $$Z_n : = \max_{i=1,\ldots,n}|X_i|.$$

I need to prove the bound

$$ E[Z_n] \leq \sqrt{2\sigma^{2}\log{n}} + \frac{4 \sigma}{\sqrt{2\log{n}}} \quad \text{for all } n \geq 2. $$

I know how to prove the bound $ E[Z_n] \leq \sqrt{2\sigma^{2}\log{n}} $ (using the moment generating function), which is even better, but the hint in the exrcise says that I should use the tail bound $$ P[|U| \geq x] \leq \sqrt\frac{2}{\pi}\frac{1}{x} e^{-\tfrac{x^2}{2}}, \quad \text{where $U$ is a standart normal r.v.} \qquad (1) $$ My idea. Since $Z_n$ is a non-negative r.v., then $$ E[Z_n] = \int_{0}^{\infty} P[Z_n \geq x] \ dx = \int_{0}^{\infty} \Bigl( 1 - \bigl(1 - P[|X_1| \geq x] \bigr)^n \Bigr) dx. $$ I tried to use the tail bound (1), but it was unsuccessful. I even don't understand why this integral converges.

I would appreciate any ideas. Thanks!

  • $\begingroup$ In the last equation there is a "dx" missing and it should read $\mathbb{P}(|X_1| \geq x)$ instead of $\mathbb{P}(X_1 \geq x)$, I think. $\endgroup$ – saz Aug 6 '16 at 15:33
  • $\begingroup$ yes, I've corrected this. $\endgroup$ – user44097 Aug 6 '16 at 16:10
  • $\begingroup$ Is anyone aware of a reference for the inequality $E[Z_n] \leq \sqrt{2\sigma^2\log{n}}?$ $\endgroup$ – stats_qs May 27 '18 at 21:44

Without loss of generality, we may assume $\sigma^2=1$ (just note that $Y_i := X_i/\sigma$ are independent standard Gaussian random variables). By Bernoulli's inequaliy, we have

$$(1-\mathbb{P}(|X_1| \geq x))^n \geq 1-n \mathbb{P}(|X_1| \geq x).$$ Hence,

$$\begin{align*} \mathbb{E}(Z_n) &= \int_0^{\infty}(1-(1-\mathbb{P}(|X_1| \geq x))^n) \, dx \\ &\leq c + \int_c^{\infty} (1-(1-\mathbb{P}(|X_1| \geq x))^n) \, dx \\ &\leq c+ n \int_c^{\infty} \mathbb{P}(|X_1| \geq x) \, dx \end{align*}$$

for any constant $c>0$. Using the tail estimate for $X_1$, we find

$$\begin{align*} \mathbb{E}(Z_n) &\leq c+ n \sqrt{\frac{2}{\pi}} \int_c^{\infty} \frac{1}{x} \exp \left(- \frac{x^2}{2} \right) \, dx \\ &\leq c+\frac{n}{c} \sqrt{\frac{2}{\pi}} \int_c^{\infty} \exp \left(- \frac{x^2}{2} \right) \, dx. \end{align*}$$

If we choose $c:= \sqrt{2 \log n}$, then $c \geq 1$ for $n \geq 2$ and therefore

$$\begin{align*} \mathbb{E}(Z_n) &\leq c + \frac{n}{c} \sqrt{\frac{2}{\pi}} \int_c^{\infty}x \exp \left(- \frac{x^2}{2} \right) \, dx \\ &= c + \frac{n}{c} \sqrt{\frac{2}{\pi}} e^{-c^2/2} \\ &= \sqrt{2 \log n} + \sqrt{\frac{2}{\pi}} \frac{1}{\sqrt{2 \log n}}. \end{align*}$$

Since $\sqrt{\frac{2}{\pi}}<1<4$, this finishes the proof.

  • $\begingroup$ The first inequality should read $(1-\mathbb{P}(|X_1| \geq x))^n \geq 1-n \mathbb{P}(|X_1| \geq x)$, isn't it? The rest seems right to me, thanks! $\endgroup$ – user44097 Aug 6 '16 at 16:06
  • $\begingroup$ @user44097 Yeah, sure, thanks $\endgroup$ – saz Aug 6 '16 at 16:07

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.