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!

  • 1
    $\begingroup$ 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\}$ $\endgroup$
    – πr8
    Oct 13, 2020 at 19:49
  • $\begingroup$ True! So I guess it's equivalent to knowing the variance and expectation of the order statistic...hmm! $\endgroup$ Oct 13, 2020 at 20:02
  • 2
    $\begingroup$ The two expectations are identical thus should cancel one another. $\endgroup$
    – Xi'an
    Oct 13, 2020 at 20:29
  • $\begingroup$ Haha, true. So really this question is just asking for the variance of the order statistics summed. $\endgroup$ Oct 13, 2020 at 20:30
  • 2
    $\begingroup$ 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. $\endgroup$
    – whuber
    Oct 13, 2020 at 22:10

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.