Difference between the largest and second largest observations from a sample of iid normal variables

Question

What can we say about the distribution of $s_1 - s_2$, where $s_1$ and $s_2$ are the largest and second largest draws from a sample of $N$ iid normal variables?

"Who's the world's greatest mathematician?" doesn't seem to be as interesting a question as it was in the days of Gauss and Euler. Might this be because there are more mathaticians in the world today, or in spite of that fact?

Imagine there are $N$ mathematicians in the world. Each mathematician's ability $a_i$ is drawn independently from a standard normal distribution. Let $s_1$ be the max of the $a_i$ and $s_2$ be the second largest of the $a_i$. What can we say about the distribution of $s_1 - s_2$?

Answer 1

We can explicitly derive the joint density of the general case of two order statistics $X_{(j)}, X_{(k)}$, $1 \le j < k \le n$, from an iid sample drawn from some continuous distribution with CDF $F(x)$. The idea is to visualize $$X_{(1)} \le \ldots \le X_{(j-1)} \le X_{(j)} \le X_{(j+1)} \le \ldots \le X_{(k-1)} \le X_{(k)} \le X_{(k+1)} \le \ldots \le X_{(n)}.$$ For a fixed $X_{(j)}, X_{(k)}$, we see that there are $$\frac{n!}{(j-1)! ((k-1)-(j+1)+1)! (n-(k+1)+1)!} = \frac{n!}{(j-1)! (k-j-1)! (n-k)!}$$ permutations that map the sample to the other $X_{(i)}$, $i \ne j, k$. Now, the probability that $j-1$ observations of $X$ are less than $x_j$, $k-j-1$ observations are between $x_j$ and $x_k$, and $n-k$ observations exceed $x_k$, is given by $$F(x_j)^{j-1} (F(x_k) - F(x_j))^{k-j-1} (1 - F(x_k))^{n-k}.$$ So we find that the joint density is $$f_{X_{(j)}, X_{(k)}}(x_j, x_k) = \frac{n! \, F(x_j)^{j-1} (F(x_k) - F(x_j))^{k-j-1} (1 - F(x_k))^{n-k} f(x_j) f(x_k)}{(j-1)! (k-j-1)! (n-k)!} .$$

For the special case that $j = n-1$, $k = n$, we then get $$f_{X_{(n-1)}, X_{(n)}}(x_{n-1}, x_n) = n(n-1) F(x_{n-1})^{n-2} f(x_{n-1}) f(x_n).$$ For $X$ a standard normal random variable, this turns out to look reasonably nice: $$f(u,v) = \begin{cases} \frac{n(n-1)}{2\pi} e^{-(u^2+v^2)/2} \Phi(u)^{n-2}, & u \le v \\ 0 & \text{otherwise}.\end{cases}$$ Now defining $W = X_{(n)} - X_{(n-1)}$, we get $$f_W(w) = \int_{u=-\infty}^\infty f(u,w+u) \, du, \quad w \ge 0.$$ This integral, to my knowledge, doesn't have an elementary closed form. I did numerically integrate the cases $n = 2^a$ for $a = 1, 2, \ldots 16$ and plotted the resulting distributions below:

This suggests that the expectation and variance of $W$ decrease with increasing $n$.

Answer 2

There are known formulas for Order Statistics. From the wiki: The $kth$ highest result drawn from $N$ outcomes of a continuous random variable with density $f_X$ and distribution $F_X$ is given by: $$f_{X(k)}(x) = \frac{n!}{(k-1)!(n-k)!}[F_X(x)]^{k-1}[1-F_X(x)]^{n-k} f_X(x)$$ The joint density of all the outcomes can be written as: $$f_{X(1),...,X(n)} = n! f_X(x_1)...f_X(x_n)$$ where $x_1 \leq ... \leq x_n$

So you can integrate out $x_1,...,x_{n-2}$ and from there calculate the statistic for $X(n) - X(n-1)$.

Answer 3

I didn't get far with that integral, but while I was working on it I wrote a Python script to simulate the process. I was surprised to see that the gap between the best and second-best mathematician shrinks on average as the population of mathematicians grows. Not clear what the asymptote is.

import numpy as np

NTRIAL = 500

def diff12(vec):
    vec_s = sorted(vec, reverse=True)
    return vec_s[0] - vec_s[1]

for nmaths in [2, 100, 1000, 100*1000]:
    obs = np.apply_along_axis(diff12, 0, np.random.normal(size=(nmaths, NTRIAL)))
    print("{:7}   {:.2f} ± {:.4f}".format(nmaths, np.mean(obs), np.std(obs)/np.sqrt(len(obs))))

Here's the output (mean difference between first and second largest value with a population of 2 to 100,000 mathematicians)

      2   1.13 ± 0.0384
    100   0.35 ± 0.0144
   1000   0.28 ± 0.0120
 100000   0.19 ± 0.0088