# Proving some properties of expected first order statistics with respect to sample size

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!

• The first order statistic is conventionally the minimum. The $n^\text{th}$ order statistic is conventionally the maximum. See, for example, here Jul 26 '14 at 8:10
• Are you derivating with respect to the sample size $n$ ? Jul 26 '14 at 9:08
• Yes @StéphaneLaurent Jul 26 '14 at 9:09
• That makes no sense to derivate with respect to an integer. What do you have in mind ? Jul 26 '14 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 Jul 26 '14 at 9:13

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. 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.

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.

• 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? Jul 26 '14 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? Jul 26 '14 at 15:38
• @gui11aum That's a good point, thank 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 '14 at 15:49
• @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 '14 at 16:25
• @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 '14 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).

$$\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)$.