# Expected squared distance between order statistics?

Suppose $$p(\cdot)$$ is a smooth probability distribution over $$\mathbb R$$. Suppose we draw two collections of $$k$$ i.i.d. samples from $$p(\cdot)$$, yielding random variables $$(X_1,\ldots,X_k)$$ and $$(Y_1,\ldots,Y_k)$$. Use $$X_{(i)}, Y_{(i)}$$ to denote the $$i$$-th order statistic of $$(X_1,\ldots,X_k), (Y_1,\ldots,Y_k)$$, resp.; that is, $$X_{(i)}$$ is the $$i$$-th value obtained when sorting the sample $$X_1,\ldots,X_k$$.

Is it possible to compute in closed-form the following expectation? $$\mathbb E_{\substack{X_1,\ldots,X_k\sim p(\cdot)\\Y_1,\ldots,Y_k\sim p(\cdot)}}\left[ \sum_{i=1}^k (X_{(i)}-Y_{(i)})^2 \right]$$ That is, is there an expression for the expected squared L2 distance between $$\vec X$$ and $$\vec Y$$ after sorting?

This answer gets part of the way, showing roughly that the expected value tends to zero as $$k\to\infty$$. This document (and many others) gives the distribution function for each $$X_{(i)}$$. If this value isn't known in closed-form, anything about its properties as a function of $$k$$ would be helpful as well!

• Possibly useful: this can be rewritten as $\sum_i \left\{ \left( \mathbb{E} X_{(i)} - \mathbb{E} Y_{(i)} \right)^2 + \text{Var} X_{(i)} + \text{Var} Y_{(i)} \right\}$
– πr8
Oct 13, 2020 at 19:49
• True! So I guess it's equivalent to knowing the variance and expectation of the order statistic...hmm! Oct 13, 2020 at 20:02
• The two expectations are identical thus should cancel one another. Oct 13, 2020 at 20:29
• Haha, true. So really this question is just asking for the variance of the order statistics summed. Oct 13, 2020 at 20:30
• In most cases this calculation can only be done numerically. (Normal distributions with $k\gt 6$ are a notable example of that.) You could probably succeed with a uniform distribution and an exponential distribution, but almost anything else is likely to be intractable. It's pretty difficult for discrete distributions, too, because of the need to account for ties.
– whuber
Oct 13, 2020 at 22:10

The terms of this sum are known exactly for some distributions, since $$E[(X_{(i)}-Y_{(i)})^2]=E[X_{(i)}^2]-2E[X_{(i)}]E[Y_{(i)}]+E[Y_{(i)}^2]=2\text{Var}[X_{(i)}].$$ For those distributions, we can get some nice expressions for the limiting behavior.
In what follows, $$\psi_1(z)$$ is the trigamma function $$d^2\log \Gamma(z)/dz^2$$, appearing in the calculation for the logistic distribution in N. Balakrishnan and A. Clifford Cohen, Order Statistics and Inference (1991), p. 40. The approximations given here with $$\sim$$ are exact in the highest-order terms.
For a uniform distribution bounded by $$0,1$$: \begin{align} \text{Var}[X_{(i:k)}]&=\frac{i(k+1-i)}{(k+1)^2(k+2)}\phantom{+123456}\\ \\ 2\sum_i\text{Var}[X_{(i:k)}]&=\frac{k}{3(k+1)}\sim\frac13 \end{align}
For an exponential distribution with mean $$1$$: \begin{align} \text{Var}[X_{(i:k)}]&=\psi_1(k+1-i)-\psi_1(k+1)\\ \\ 2\sum_i\text{Var}[X_{(i:k)}]&\sim 2\log k+1 \end{align}
For a logistic distribution with parameters 0,1: \begin{align} \text{Var}[X_{(i:k)}]&=\psi_1(k+1-i)+\psi_1(k)\phantom{+12}\\ \\ 2\sum_i\text{Var}[X_{(i:k)}]&\sim 4\log k+8 \end{align}
For the unbounded distributions, these are growing functions: the answer linked in the question shows $$\frac{1}{k}\|X-Y\|_1\to 0$$, while this is showing $$\|X-Y\|_2^2\to \infty$$.