I have a problem where my errors are normally distributed and I want to know what the expected maximum error is if I repeat the process $n$ times.

What is the smallest constant $C$ such that the following statement is true for all $n\geq 2$?

Let $X_1, X_2, \cdots, X_n$ be independent standard Gaussian random variables. Then $$\mathbb{E}\left[\max_{i=1}^n \left|X_i\right| \right] \leq C \sqrt{\log_e n}.$$

I can show that the answer is between $1.35$ and $2$.


The inequality holds with $C=\sqrt{2}$, and this is the optimal constant (the optimality follows from here).

Outline of the proof:

  1. Let $\varphi$ and $\Psi$ be the pdf and complementary cdf of standard normal distribution. Using the inequality $\Psi(x)< \varphi(x)/x$ for $x>0$, it is easy to show that $-\log \Psi(x)$ is convex, therefore, its inverse $G(t) = \Psi^{-1}(e^{-t})$ is concave. Note also that $G$ is increasing.

  2. Applying the quantile transformation, $X_k = G(Y_k)$, where $Y_k$ are iid $\operatorname{Exp}(1)$. Denoting $X_{(n)} = \max_k X_k$, $Y_{(n)} = \max_k Y_k$ and using the monotonicity and concavity of $G$, we get with the help of Jensen's inequality $$ E[X_{(n)}] = E[G(E_{(n)})]\le G(E[Y_{(n)}]) = G(H_n), $$ where $H_n = 1+\frac12 + \dots + \frac1n$ is the $n$th harmonic number (the distribution of exponential order statistics is well known). Since $H_n\le \log n + 1$ for all $n$, we get $$ E[X_{(n)}]\le G(\log n+1) = \Psi^{-1}\big(\tfrac1{en}\big). $$

  3. Using the inequality $\Psi(x)< \varphi(x)/x$ again, $$ \Psi(\sqrt{2 \log n}) \le \frac{1}{2\sqrt{\pi\log n}}e^{-\log n} \le \frac{1}{en}. $$ As $\Psi$ decreases, $$ E[X_{(n)}]\le \sqrt{2\log n}, $$ as required.

| cite | improve this answer | |

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.