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

Question

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!

Answer 1

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.

---

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.

Answer 2

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