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

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.

• I presume you mean $X_1,...,X_n,Y_1,...,Y_n$ have the same distribution, rather than have the same limiting distribution. In other words $X_1,...,X_n,Y_1,...,Y_n$ are iid. When you say $X_1 \leq \cdots X_n$ and similarly for the $Y$ variables, you should change your notation to the conventional order-statistic notation, though I'm not sure how this is relevant when you are interested in the $L_1$ norm scaled by $\frac{1}{n}$. Please edit your post to clarify this.
– dlnB
Mar 27 '19 at 18:24
• Or did you mean that the sequence of X and the sequence of Y both converge to the same distribution? If so, I’ll edit my answer below.
– dlnB
Mar 27 '19 at 18:46
• I adjusted my question by adding a simple example. Scaling by $\frac{1}{n}$ is essential because it corrects for infinitely many small errors that accumulate in the limit. A further simplification would indeed be that $X_i$ and $Y_i$ are i.i.d. (don't think that this affect the essence of the problem). Apr 8 '19 at 14:01
• (+1) Here is a hint: Convergence in probability does not hold, in general, (a) even if all $X_i$ and $Y_i$ are jointly iid if we drop the moment condition, or (b) even in the case of uniformly bounded independent random variables. To deepen the hint, recall that (a) all continuous random variables can be constructed from uniforms and (b) constants are random variables. Apr 14 '19 at 16:08

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

• That is why the sorting is essential. In the limit $X_1$ will become closer and closer to $Y_1$, $X_2$ to $Y_2$ etc. I adjusted my question with a simple example. Apr 8 '19 at 14:05
• @Nicolas When you say "sorted" I guess you refer to order statistics? Apr 8 '19 at 18:45
• Yes, indeed. I should have been more clear indeed. Apr 8 '19 at 19:24