Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Question: Consider $n$ random variables $x_1, x_2,\cdots x_n\sim \mathcal{N}(0,1)$. The expected value of the $i$th order statistic (the maximum) can be written as

$E(\mathcal{O}^n_1)= \displaystyle\int_{-\infty}^{+\infty}nx\Phi(x)^{n-1}\phi(x)\:dx$.

I wish to show that for $n_1<n_2<n_3$,

$E(\mathcal{O}^{n1}_1)<E(\mathcal{O}^{n2}_1)<E(\mathcal{O}^{n3}_1)$, and

$E(\mathcal{O}^{n3}_1)-E(\mathcal{O}^{n2}_1)<E(\mathcal{O}^{n2}_1)-E(\mathcal{O}^{n1}_1)$,

where $\mathcal{O}^{n1}_1$ is the first order statistic (maximum) for a sample of $n1$.

Progress so far I've managed to prove the part for first-order derivative by invoking the concept of first-order stochastic dominance. But still no progress on the second-order...

Any help will be greatly appreciated. Thanks!

share|improve this question
1  
The first order statistic is conventionally the minimum. The $n^\text{th}$ order statistic is conventionally the maximum. See, for example, here –  Glen_b Jul 26 at 8:10
    
Are you derivating with respect to the sample size $n$ ? –  Stéphane Laurent Jul 26 at 9:08
    
Yes @StéphaneLaurent –  Jacob Yerger Jul 26 at 9:09
    
That makes no sense to derivate with respect to an integer. What do you have in mind ? –  Stéphane Laurent Jul 26 at 9:10
    
Let me modify: Essentially I just wanted to show submodularity, i.e., for n1<n2<n3, O(n3)-O(n2)<O(n2)-O(n1) @StéphaneLaurent –  Jacob Yerger Jul 26 at 9:13

2 Answers 2

up vote 3 down vote accepted

Let's simplify the notation and write $e(n)$ for the expectation of the maximum of $n$ iid Normal$(0,1)$ variables $X_1, X_2, \ldots, X_i, \ldots, X_n$, with $n$ arbitrary.


The first claim is that $e$ is monotonically increasing; that is, $e(m) \lt e(n)$ whenever $0\lt m\lt n$. This is immediate from two simple observations:

  • $\max\{X_1, \ldots, X_m\} \le \max\{X_1,\ldots, X_m,\ldots, X_n\}$ (implying $e(m)\le e(n)$) and

  • There is a positive chance that the maximum of all $n$ of the $X_i$ will strictly exceed the maximum of the first $m$ of them (implying the inequality is strict).


The second claim is that all increments in $e$ are strictly decreasing; that is, whenever $0\lt n_1\lt n_2\lt n_3$ then $e(n_3)-e(n_2) \lt e(n_2) - e(n_1)$. This is false.

Such a result would imply that $e(n) \lt 2e(n_2) - e(n_1)$ for all $n\gt n_2$, providing a set of finite upper bounds on the entire sequence $e(1), e(2), \ldots, e(n), \ldots$. Yet, to the contrary, the maximum of a large number of (independent) Normal variables must be concentrated around an arbitrarily large value. This is immediate from the Fisher-Tippett-Gnedenko theorem on extreme value distributions, but there is a nice elementary demonstration. It relies on the fact that when random variables $X$ and $Y$ have distributions with CDFs $F$ and $G$, respectively, then the difference in their expectations equals the (signed) area between the graphs of $F$ and $G$, as shown by integrating that difference by parts:

$$\mathbb{E}(Y) - \mathbb{E}(X) = \int_\mathbb{R} x dG(x) - \int_\mathbb{R} x dF(x) = \int_\mathbb{R} (G(x)-F(x))dx.$$

To apply this let $F$ be the common CDF of the $X_i$. Pick any number $N\gt 0$. Since for the standard Normal distribution $F(N+1)\lt 1$, we can find a positive integer $n$ for which $F(N+1)^n \le 1/(N+1)$, as in the figure.

Figure

The gold curve is the graph of $F$ and the blue curve is the graph of $F^n$.

Let $Y = \max(X_1, \ldots, X_n)$. Because the $X_i$ are independent, $G(x) = F(x)^n$. The difference in expectations, $\mathbb{E}(Y) - \mathbb{E}(X) = e(n) - e(1)$, therefore equals the blue area in the figure. The figure shows this area decomposed into four parts, $I$ (all the blue to the left of $0$), $III, IV$, and $V$. Areas $I$ and $II$ are fixed and finite (because $X$ has finite expectation equal to the area of $II$ minus the area of $I$). Areas $II$ and $III$ comprise a rectangle of base $N+1$ and height $1-1/(N+1)$, whence its area equals $N$. Consequently--ignoring the contributions of $IV$ and $V$ altogether--an underestimate of $e(n)$ is given by $N$ plus the area of $II$ minus the area of $I$. (The symmetry of the standard Normal distribution implies $I$ and $II$ are congruent, showing the difference of their areas is zero.)

This simple visualization shows there always exists an $n$ for which $e(n) \gt N$ no matter what value $N$ might have. Therefore the sequence $(e(n))$ cannot be bounded above.


Discussion and Comments

This argument made no reference to the actual expression for $F$. It needed only two assumptions:

  1. $F(x)\lt 1$ for all $x$. (That is, the $X_i$ have unbounded support.)

  2. The $X_i$ are independent.

Consequently the conclusions hold for a large family of distributions, not just the Normal distribution, and these distributions need not even be continuous.

Incidentally, $n$ must be very large even for small $N$. For the standard Normal distribution, the values of $n$ for $N=1, 2, 3, 4$ are $5, 48, 1027, 50817$. Thus, it can be difficult to find counterexamples to claim (2) via simulations unless very large values of $n$ are involved. This provides a nice example of how simulations alone can be misleading: some mathematical analysis is essential to make sure the simulations are useful and are properly interpreted.

share|improve this answer
    
Good job, to the point as usual. I am not sure about the last argument though. A bound on the expectation of the maximum of $n$ variables is not necessarily a bound on the distribution itself, is it? –  gui11aume Jul 26 at 15:15
    
Thanks for your explanation and your patience. I am probably still overthinking this :-) Take $X_1, ..., X_n$ with a Gaussian distribution, but such that $X_1 = X_2 = \ldots = X_n$. Now $e(n) = 0$ and 123 is an upper bound. Taking the expectation changes the deal, doesn't it? –  gui11aume Jul 26 at 15:38
1  
@gui11aum That's a good point, than you. I was hoping to circumvent a slightly more technical demonstration of the falseness of the second claim, but it looks like in so doing I resorted to a fallacious argument. I'll edit that. –  whuber Jul 26 at 15:49
1  
@gui11aume Yes, that's correct. I made a mention of that in my edit, but I don't need to invoke the full theory in the argument, which amounts to making a set of elementary bounds on the expectation. Evidently when independence does not hold, we need enough "residual independence" to get the same asymptotic behavior of the CDF of the maximum. –  whuber Jul 26 at 16:25
1  
@gui11aume In light of this discussion--which I greatly appreciate for having given me the opportunity to improve a deficient answer--I will delete my first comment, which is misleading. –  whuber Jul 26 at 16:30

I implicitly assume that the variables are independent.

If you replace $<$ by $\leq$, the first property is true of every distribution. Here is a general proof using measure theory. Starting from $\max(X,Y) \geq X$ we get

$$ E\left(\max(X,Y)\right) = \int \max(X,Y) dP \geq \int X dP = E(X).$$

Since $\max(X_1, \ldots, X_{n_2}) = \max\left(\max(X_1, \ldots, X_{n_1}),\max(X_{n_1+1}, \ldots, X_{n_12})\right)$, the formula above shows that $E\left(\max(X_1, \ldots, X_{n_2})\right) \geq E\left(\max(X_1, \ldots, X_{n_1})\right)$.

In the proof above, the variables $X_1, \ldots, X_{n_1}$ are shared between the two sets. If this is not the case, i.e. $n_1 < n_2$ but the samples are independent, the property still holds but another proof is needed. Taking the difference $E(\mathcal{O}_1^{n_2}) - E(\mathcal{O}_1^{n_1})$, we get

$$\int n_1 x\Phi(x)^{n_1-1}\phi(x) \left(\frac{n_2}{n_1}\Phi(x)^{n_2-n_1} - 1\right)dx.$$

The term between parentheses is a non decreasing function of $x$ and is positive for large values of $x$. Define $x_0$ the smallest value such that this term is positive, i.e. $\Phi(x_0)^{n_2-n_1} = n_1/n_2$. For now, assume $x_0 > 0$. It is easy to check that if $f$ is a non decreasing function and $f(x_0) = 0$ for $x_0 > 0$, then $xf(x) \geq x_0f(x)$ for all $x > 0$. Using $f(x) = n_1 \Phi(x)^{n_1-1}\phi(x) \left(\frac{n_2}{n_1}\Phi(x)^{n_2-n_1} - 1\right)$ yields

$$x \left(n_2\Phi(x)^{n_2-1}\phi(x) - n_1\Phi(x)^{n_1-1}\phi(x)\right) \geq x_0 \left(n_2\Phi(x)^{n_2-1}\phi(x) - n_1\Phi(x)^{n_1-1}\phi(x)\right).$$

Since the integral is non negative over $(-\infty, 0)$ we obtain $$E(\mathcal{O}_1^{n_2}) - E(\mathcal{O}_1^{n_1}) \geq x_0 \int_{0}^{+\infty}n_2\Phi(x)^{n_2-1}\phi(x) - n_1\Phi(x)^{n_1-1}\phi(x)dx = \\ x_0 \left(\Phi(0)^{n_1}-\Phi(0)^{n_2}\right) \geq 0.$$

The case $x_0 < 0$ is treated in a similar way and gives a lower bound equal to $x_0\left( \Phi(0)^{n_2} - \Phi(0)^{n_1}\right)$. In the case $x_0 = 0$, the integral is always positive and there is nothing to prove. I never used the properties of the Gaussian, so this proof is valid for every distribution with finite expected value; for non continuous distribution $\phi(x)dx$ has to be replaced by an appropriate probability measure. If the distribution has unbounded support, the inequality is strict.

The second property is false. Take $n_1 = 1$, $n_2 = 2$ while $n_3$ goes to $\infty$. The right hand side is finite, while the left hand side is unbounded because the maximum of $n$ Gaussian has asymptotic distribution

$$F(x) = e^{-\exp \left(-\frac{x-b_n}{a_n}\right)},$$

where $b_n \uparrow \sqrt{2\log(n)-\log(\log(n))-\log(4\pi)}$ and $a_n = 1 / b_n$ (see for instance this page).


Comments and connection with the answer of @whuber:
The proof of @whuber is simpler and more graphical than mine. Integrating by parts indeed gives the result of the first part immediately, the reason I decided not use this approach is because it pops out infinite terms out of the integral and I did not find the conditions where they cancel out.

One advantage of the approach above, which I did not realize immediately, is that it gives an easy (non graphical) proof of the statement

$$\lim_{n\rightarrow \infty} E\left(max(X_1, \ldots, X_n)\right) - E(X) = +\infty\ \text{iff}\ \forall x \in \mathbb{R}, F(x) < 1.$$

To see this, observe that $\lim_{n_2 \rightarrow \infty} \frac{1}{n_2-1} \log(n_2) = 0$, so $\lim_{n_2 \rightarrow \infty} \left(\frac{1}{n_2}\right)^{1/(n_2-1)}= 1$. As a consequence, the solution of $\Phi(x_0)^{n2-1} = \frac{1}{n_2}$ tends to infinity if and only if $\forall x \in \mathbb{R}, F(x) < 1$ and in this case $x_0$ tends to infinity, and so does the lower bound $x_0 \left(\Phi(0)^{n_1}-\Phi(0)^{n_2}\right)$.

share|improve this answer
1  
+1 especially for making the explicit connection with extreme value theory at the end (and the link to a very clear and useful reference). –  whuber Jul 26 at 16:30

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.