Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there an exact or good approximate expression for the expectation, variance or other moments of the maximum of $n$ independent, identically distributed gaussian random variables where $n$ is large?

If $F$ is the cumulative distribution function for a standard gaussian and $f$ is the probability density function, then the CDF for the maximum is (from the study of order statistics) given by

$$F_{\rm max}(x) = F(x)^n$$

and the PDF is

$$f_{\rm max}(x) = n F(x)^{n-1} f(x)$$

so it's certainly possible to write down integrals which evaluate to the expectation and other moments, but it's not pretty. My intuition tells me that the expectation of the maximum would be proportional to $\log n$, although I don't see how to go about proving this.

share|improve this question
    
I presume you are interested in the large $n$ regime ? –  Sasha Dec 6 '11 at 21:26
    
@Sasha yes, I'll edit to include that –  Chris Taylor Dec 6 '11 at 21:38
    
You might be interested in this related question: Does exceptionalism persist as sample size gets large? –  Mike Spivey Dec 7 '11 at 5:28
    
Note: the answers to this related question on cstheory.stackexchange are useful in answering your question. –  Neal Young Dec 4 '12 at 23:31
add comment

2 Answers 2

up vote 20 down vote accepted

The $\max$-central limit theorem (Fisher-Tippet-Gnedenko theorem) can be used to provide a decent approximation when $n$ is large. See this example at reference page for extreme value distribution in Mathematica.

The $\max$-central limit theorem states that $F_\max(x) = \left(\Phi(x)\right)^n \approx F_{\text{EV}}\left(\frac{x-\mu_n}{\sigma_n}\right)$, where $F_{EV} = \exp(-\exp(-x))$ is the cumulative distribution function for the extreme value distribution, and $$ \mu_n = \Phi^{-1}\left(1-\frac{1}{n} \right) \qquad \qquad \sigma_n = \Phi^{-1}\left(1-\frac{1}{n} \cdot \mathrm{e}^{-1}\right)- \Phi^{-1}\left(1-\frac{1}{n} \right) $$ Here $\Phi^{-1}(q)$ denotes the inverse cdf of the standard normal distribution.

The mean of the maximum of the size $n$ normal sample, for large $n$, is well approximated by $$ \begin{eqnarray} m_n &=& \sqrt{2} \left((\gamma -1) \Phi^{-1}\left(1-\frac{1}{n}\right)-\gamma \Phi^{-1}\left(1-\frac{1}{e n}\right)\right) \\ &=& \sqrt{\log \left(\frac{n^2}{2 \pi \log \left(\frac{n^2}{2\pi} \right)}\right)} \cdot \left(1 + \frac{\gamma}{\log (n)} + \mathcal{o} \left(\frac{1}{\log (n)} \right) \right) \end{eqnarray}$$ where $\gamma$ is the Euler-Mascheroni constant.

share|improve this answer
    
+1. See also Section 10.5 ("The Asymptotic Distribution of the Extreme") in David and Nagaraja's Order Statistics. They explicitly discuss the normal distribution on page 302. –  Mike Spivey Dec 6 '11 at 22:35
    
@MikeSpivey Yes, I meant $\max$-central limit theorem. I have edited the post to precise that. Thank you. –  Sasha Dec 6 '11 at 22:51
    
Doesn't the inverse cdf have domain $[0,1]$? –  Geoffrey Irving Dec 30 '12 at 7:01
    
@GeoffreyIrving Thanks for catching this. It is a typo. –  Sasha Dec 30 '12 at 14:39
4  
(+1) Two comments: (1) The somewhat nonstandard use of $Q$ for the inverse normal is a little unfortunate given that it is a standard notation in some contexts for the upper-tail distribution of the standard normal $\mathbb P(Z \geq z)$. I would suggest $\Phi^{-1}$ instead. (2) As you know, convergence in distribution doesn't imply convergence of moments, in general; but, in the case of extreme values of iid random variables it does (curiously enough). This was proved in Pickands (1968). –  cardinal Dec 30 '12 at 16:19
add comment

How precise an answer are you looking for? Giving (upper) bounds on the maximum of i.i.d Gaussians is easier than precisely characterizing its moments. Here is one way to go about this (another would be to combine a tail bound on Gaussian RVs with a union bound).

Let $X_i$ for $i = 1,\ldots,n$ be i.i.d $\mathcal{N}(0,\sigma^2)$.

Defining, $$ Z = [\max_{i} X_i] $$

By Jensen's inequality,

$$\exp \{t\mathbb{E}[ Z] \} \leq \mathbb{E} \exp \{tZ\} = \mathbb{E} \max_i \exp \{tX_i\} \leq \sum_{i = 1}^n \mathbb{E} [\exp \{tX_i\}] = n \exp \{t^2 \sigma^2/2 \}$$

where the last equality follows from the definition of the Gaussian moment generating function (a bound for sub-Gaussian random variables also follows by this same argument).

Rewriting this,

$$\mathbb{E}[Z] \leq \frac{\log n}{t} + \frac{t \sigma^2}{2} $$

Now, set $t = \frac{\sqrt{2 \log n}}{\sigma}$ to get

$$\mathbb{E}[Z] \leq \sigma \sqrt{ 2 \log n} $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.