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.

  • 2
    $\begingroup$ Actually $E(M_n)\leqslant\sigma\sqrt{2\log n}$ is a one-line computation. $\endgroup$ – Did Oct 25 '14 at 15:31
  • $\begingroup$ Mmh, I just realized my question was slightly wrong, as phrased. I should have written $\Theta(1)$ instead of $O(1)$ (for both upper and lower bound). $\endgroup$ – Clement C. Oct 25 '14 at 15:36

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)

  • $\begingroup$ @Chill2Macht How so? Look e.g. at the discussion after the proof (specifically equation (3.26)) in [2]; or as mentioned above Exercise 2.17 in [1]. $\endgroup$ – Clement C. Feb 18 '18 at 2:10
  • $\begingroup$ The discussion near 3.26 [2] is helpful, but one has to prove first that the max is sub-Gaussian before being able to use it. Thankfully theorem 5.8 from [1] gives a proof of that, which does help. I have to admit that when I complained I didn't actually bother looking at Theorem 5.8 because I didn't see how it could help with this problem, since the earlier parts of [1] mentioned did not seem very helpful. $\endgroup$ – Chill2Macht Feb 18 '18 at 22:35
  • 1
    $\begingroup$ @Chill2Macht Starting with 1.: No. Why would you have a $\sqrt{n}$ in the denominator, while the first expression has a $\sqrt{2\log n}$? $\endgroup$ – Clement C. Sep 21 '18 at 1:44
  • 1
    $\begingroup$ @Chilll2Macht i think the best way to proceed is by asking a new question, with a link to this one possibly. $\endgroup$ – Clement C. Sep 21 '18 at 2:00
  • 1
    $\begingroup$ stats.stackexchange.com/questions/367942/… It seems I was wrong on both counts. $\endgroup$ – Chill2Macht Sep 22 '18 at 23:13

You have an explicit asymptotic result concerning the limit distribution in this post and the associated references.


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.