Convergence of scaled $L_1$ distance between two sorted random vectors with same limiting distribution

Question

Let $ X=(X_1,\dots,X_n) $ and $ Y=(Y_1,\dots,Y_n) $ where the RVs $ X_1,\dots X_n, Y_1,\dots Y_n $ are independent and have the same limiting distribution (assume for simplicity that all moments exist). Furthermore let $ X_1 \leq X_2 \leq \dots \leq X_n $ and $ Y_1 \leq Y_2 \leq \dots \leq Y_n $ (so each vector is sorted). Can we say that $ \frac{1}{n} \left\Vert X-Y \right\Vert _1 \rightarrow 0 $, either in probability or almost surely?

As a simple example, let $ X_i \thicksim N(0,1) $ and $ Y_i \thicksim N(0,1)+\frac{1}{n}U(0,1) $, so that their asymptotic distributions are equivalent. Then it is evident from simulations that for large $n$ the scaled distance $ \frac{1}{n} \left\Vert X-Y \right\Vert _1 \rightarrow 0 $ only if the vectors $X$ and $Y$ are sorted.

Answer 1

As has been clarified, the OP refers to order statistics. Also I will treat the case of i.i.d. random variables. It is my impression that this is equivalent to assume non-identically distributed elements of the sequence but converging to a limit distribution and hence, eventually having "virtually the same distribution" infinitely many times.

Moreover I will assume that the limiting distribution is continuous. I don't think that my "sandwich" argument carries over if the limiting distribution is discrete.

The treatment does not appear to be fully rigorous, but I think it is on the right track.

Using standard notation for order statistics, since the sample is i.i.d,, it is also ergodic and so by Kinchin's LLN

$$\frac 1n \sum_{i=1}^{n} |X_{(i)}-Y_{(i)}| - \frac 1n \sum_{i=1}^{n} E|X_{(i)}-Y_{(i)}|\to_p 0 $$

We want to show that (deterministic limit here)

$$\frac 1n \sum_{i=1}^{n} E|X_{(i)}-Y_{(i)}|\to 0$$

If only a finite number of the elements of the series remains non-zero as $n\to \infty$, then this average of expected values will go to zero. So we need an infinite number of $E|X_{(i)}-Y_{(i)}|$ elements to go to zero. I don't see why for some order statistics this term could stay away from zero while for an infinite number of them it could go to zero, so I conclude that we need to prove (or at least it is sufficient to prove) that

$$\forall i,\;\; E|X_{(i)}-Y_{(i)}| \to 0$$

But the expected value of an absolute value will be equal to zero only if the term inside the absolute value will be equal to zero. So we end up needing/wanting to prove that

$$\forall i,\;\; X_{(i)}-Y_{(i)} \to_p 0$$

Now, the Empirical Distribution Function for the $Y$'s is

$$\hat F_{Y,n}(s) = \frac 1n \sum_{j=1}^n I\{Y_j \leq s\}$$

The EDF converges strongly to the true distribution function,

$$\frac 1n \sum_{j=1}^n I\{Y_j \leq s\} \to_{as} F_{Y}(s) = \Pr(Y^*\leq s) \equiv p_s$$

where the star indicates the limiting random variable. The probability $p_s$ is a given number and it can be expressed as

$$p_s = \lim_{n \to \infty}\frac {m(s,n)}{n}$$

where $m$ is the index of the $m$-th order statistic and the expression $m(s,n)$ indicates that its value will depend on $p_s$ as well as on the sample size. This implies that

$$\text{plim} Y_{(m)} \leq s,\;\;\; s < \text{plim} Y_{(m+1)}\leq s',\;\;\; s'>s$$

We can apply exacty the same treatment on the $X$'s and obtain (using $r$ to denote the value of the order statistic here)

$$p_s = \lim_{n \to \infty}\frac {r(s,n)}{n}$$

This is the same $p_s$ as before because by the premises the limiting distribution is the same. So

$$ r(s,n) - m(s,n) \to 0$$ So, we also have

$$\text{plim} X_{(r)} \leq s,\;\;\; s < \text{plim} X_{(r+1)}\leq s',\;\;\; s'>s$$

Combining the two two-sided inequalities we have

$$s-s' < \text{plim}\big[ X_{(r+1)} - Y_{(m+1)}\big] < s'-s$$

But since we examine a continuous limiting distribution, at the limit $s'$ could be arbitrarily close to $s$ and still the above should hold since we have strong convergence of the empirical distribution function. But then, together with $r(s,n)-m(s,n) \to 0$, we have sandwiched the $\text{plim}$ of $X_{(r+1)} - Y_{(m+1)}$ to zero, namely,

$$\forall i,\;\; X_{(i)}-Y_{(i)} \to_p 0$$

indeed... except perhaps for the minimum order and the maximum order statistic for limiting distributions that have support open to plus/minus infinity, for which a different proof appears to be needed.