Probability Theory – Reference for Gaussian Inequality (E[max_i X_i])

normal distributionprobability distributionsprobability theory

I am looking for a reference to cite, for the following "folklore" asymptotic behaviour of the maximum of $n$ independent Gaussian real-valued random variables $X_1,\dots, X_n\sim \mathcal{N}(0,\sigma)$ (mean $0$ and variance $\sigma^2$):
$$
\mathbb{E} \max_i X_i = \sigma\left(\tau\sqrt{\log n}+\Theta(1)\right)
$$
(where, if I'm not mistaken, $\tau=\sqrt{2}$). I've been pointed to a reference book of Ledoux and Talagrand, but I can't see the satement "out-of-the-box" there — only results that help to derive it.

Best Answer

I eventally found these two references:

  • from [1]: the expected value of the maximum of $N$ independent standard Gaussians: Theorem 2.5 and Exercise 2.17, p. 49; for a concentration result, combined with the variance (which is $O(1)$). Exercise 3.24 (or Theorem 5.8 for directly a concentration inequality).
  • from [2], Theorem 3.12

[1] Concentration Inequalities: A Nonasymptotic Theory of Independence By Stéphane Boucheron, Gábor Lugosi, Pascal Massart (2013)

[2] Concentration Inequalities and Model Selection, by Pascal Massart (2003)

Related Question