# Expectation of the maximum absolute value of gaussian random variables

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!

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

• 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! – user44097 Aug 6 '16 at 16:06
• @user44097 Yeah, sure, thanks – saz Aug 6 '16 at 16:07