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
    Commented Aug 6, 2016 at 15:33
  • $\begingroup$ yes, I've corrected this. $\endgroup$
    – user44097
    Commented Aug 6, 2016 at 16:10
  • 2
    $\begingroup$ Is anyone aware of a reference for the inequality $E[Z_n] \leq \sqrt{2\sigma^2\log{n}}?$ $\endgroup$
    – stats_qs
    Commented May 27, 2018 at 21:44

1 Answer 1


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
    Commented Aug 6, 2016 at 16:06
  • $\begingroup$ @user44097 Yeah, sure, thanks $\endgroup$
    – saz
    Commented Aug 6, 2016 at 16:07
  • $\begingroup$ Doesn't the estimate with Bernoulli's inequality follow from the union bound? Is independence really needed? $\endgroup$ Commented Mar 29 at 20:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .