# Conditions for the convergence of two sorted vectors of samples

Let $X$ be a random variable and $X_1, X_2, \ldots, X_n$ be a sample of size $n$ and $X_{(1)},X_{(2)},\ldots,X_{(n)}$ the corresponding order statistics, which are obtained by sorting the values $X_1, X_2, \ldots, X_n$. Let's draw a new sample of size $n$ with the corresponding order statistics $X'_{(1)},X'_{(2)},\ldots,X'_{(n)}$.

It seems that the Pearson linear correlation between $X_{(1)},X_{(2)},\ldots,X_{(n)}$ and $X'_{(1)},X'_{(2)},\ldots,X'_{(n)}$ (two vectors of $n$ sorted samples from the same distribution) converges to $1$ as $n$ tends to infinity, i.e.:

$$\frac{\sum_{i=1}^n(X_{(i)}-\bar{X})(X'_{(i)}-\bar{X'})} {\sqrt{\sum_{i=1}^n(X_{(i)}-\bar{X})^2} \sqrt{\sum_{i=1}^n(X'_{(i)}-\bar{X'})^2}} \overset{\text{a.s.}}{\to}1$$ as $n\to\infty$ where $\bar{X}=\frac{1}{n}\sum_{i=1}^nX_{(i)}$ and $\bar{X'}=\frac{1}{n}\sum_{i=1}^nX'_{(i)}$.

The convergence may be intuitively shown with R: n <- 1e4 ; cor(sort(rlnorm(n)), sort(rlnorm(n))) which gives results that are closer and closer to 1 as n grows.

This seems to be a simple problem, but I could not find any reference on this. Which convergence is it (almost sure, ...) and what are the conditions on the distribution for such a convergence?

• $X_1,\ldots,X_n$ is one sample of size $n$, not $n$ samples. ${}\qquad{}$ – Michael Hardy Oct 5 '15 at 19:50
• I just edited the question to make it clearer. The R code shows the practical context, all the mathematical notations being an attempt to formalize the question. – Louis-Claude Canon Oct 6 '15 at 12:32
• I think it was clear enough what was being said even though at least two things (one of which I mentioned above) were not as well expressed as they could have been. In its current state, the question is clear. – Michael Hardy Oct 6 '15 at 17:41
• Using law of large numbers and identities such as $\bar X=\frac1n\sum\limits_iX_{(i)}=\frac1n\sum\limits_iX_i\to E(X)$, $\frac1n\sum\limits_iX_{(i)}^2=\frac1n\sum\limits_iX_i^2\to E(X^2)$, $\frac1n\sum\limits_i(X_{(i)}-\bar X)^2=\frac1n\sum\limits_iX_i^2-(\bar X)^2\to E(X^2)-E(X)^2$, one is reduced to show that $$\frac1n\sum_iX_{(i)}X'_{(i)}\to E(X^2),$$ almost surely. Any idea for this last step? – Did Oct 6 '15 at 19:22
• This is indeed the crux. MC simulations suggest this is true, so I would have expected to see this result in a textbook. This is either not so simple or not true. My idea was to state that $X_{(i)}$ converges to a quantile and that $\frac{1}{n}\sum_i$ is similar to the integral $\int_x dx$ as $n\to\infty$. Something similar to $\frac{1}{n}X_{(i)}X'_{(i)}\to\int_x q(x)^2dx$. But this is just intuition. – Louis-Claude Canon Oct 7 '15 at 6:53

With two colleagues, we were able to prove the convergence in probability for the uniform distribution. We use the fact that it is sufficient to prove that the expected value of the correlation tends to 1 and its variance tends to 0 as $n\to\infty$ to prove the convergence in probability (this can be proved by using Chebyshev's inequality).

Continuing the proof in the previous comment, we want to study the limit of $E\left[S_n\right]=E\left[\frac1{n}\sum_{i=1}^nX_{(i)}X^\prime_{(i)}\right]$ as $n\to\infty$.

\begin{eqnarray} E\left[S_n\right] & = & \frac1{n} \sum_{i=1}^n E\left[X_{(i)}X^\prime_{(i)}\right] \\ & = & \frac1{n} \sum_{i=1}^n E\left[X_{(i)}\right] E\left[X^\prime_{(i)}\right] \end{eqnarray}

The expectation of the ordered statistics for the uniform distribution is $E\left[X_{(i)}\right]=\frac{i}{n+1}$.

Thus, $E\left[S_n\right]=\frac1{n} \sum_{i=1}^n\left(\frac{i}{n+1}\right)^2=\frac1{n(n+1)^2}\sum_{i=1}^n i^2=\frac1{6}\frac{(2n+1)}{(n+1)}$.

Therefore, $E\left[S_n\right]\to\frac{1}{3}$ as $n\to\infty$, which is indeed equal to $E\left[X^2\right]=V\left[X\right]+E\left[X\right]^2=\frac1{12}+\frac1{2}^2$ for the uniform distribution.

Now, let's consider the limit of the variance:

\begin{align*} S_n^2&=\frac{1}{n^2}\left(\sum_{i=1}^n X_{(i)}X_{(i)}^\prime\right)^2\\ &\leq \frac{1}{n^2}\left(\sum_{i=1}^n\left( \frac{1}{2}X_{(i)}^2+\frac{1}{2}{X_{(i)}^\prime}^2\right)\right)^2\\ &= \frac{1}{n^2}\left[\left(\frac{1}{2}\sum_{i=1}^n X_{(i)}^2\right)^2+\left(\frac{1}{2}\sum_{i=1}^n{X_{(i)}^\prime}^2\right)^2+2\left(\frac{1}{2}\sum_{i=1}^n X_{(i)}^2\right)\left(\frac{1}{2}\sum_{i=1}^n{X_{(i)}^\prime}^2\right)\right]\\ \end{align*}

Since $E\left[\sum_{i=1}^n{X_{(i)}^\prime}^2\right]=E\left[\sum_{i=1}^n{X_{(i)}}^2\right]$, we have

\begin{align*} E[S_n^2]&\leq \frac{1}{n^2}E\left[\left(\sum_{i=1}^nX_{(i)}^2\right)^2\right] \end{align*}

Thus,

\begin{align*} E[S_n^2]-E[S_n]^2&\leq \frac{1}{n^2}E\left[\left(\sum_{i=1}^nX_{(i)}^2\right)^2\right]-E[S_n]^2\\ &=E\left[\left(\frac{1}{n}\sum_{i=1}^nX_{(i)}^2\right)^2-E[S_n]^2\right]\\ &=E\left[\left(\left(\frac{1}{n}\sum_{i=1}^nX_{(i)}^2\right)-E[S_n]\right)\left(\left(\frac{1}{n}\sum_{i=1}^nX_{(i)}^2\right)+E[S_n]\right)\right]\\ \end{align*}

Let $A_n=\left(\frac{1}{n}\sum_{i=1}^nX_{(i)}^2\right)-E[S_n]$ and $B_n=\left(\frac{1}{n}\sum_{i=1}^nX_{(i)}^2\right)+E[S_n]$.

We have thus

$$E[S_n^2]-E[S_n]^2\leq E[A_nB_n]$$

Since each $X_{(i)}$ is between $0$ and $1$, and $E[S_n]\leq 1/3$, we have $0\leq B_n\leq 1+1/3=4/3$. This means that

$$E[S_n^2]-E[S_n]^2\leq \frac{4}{3}E[A_n]$$

But since

\begin{align*} E[A_n]&= E\left[\left(\frac{1}{n}\sum_{i=1}^nX_{(i)}^2\right)-E[S_n]\right]\\ &=E\left[\left(\frac{1}{n}\sum_{i=1}^nX_{(i)}^2\right)\right]-E[S_n]\\ &=\left(\frac{1}{n}\sum_{i=1}^n E\left[X_{(i)}^2\right]\right)-E[S_n]\\ &=\left(\frac{1}{n}\sum_{i=1}^n \left(V\left[X_{(i)}\right]+E[X_{(i)}]^2\right)\right)-E[S_n]\\ &=\frac{1}{n}\sum_{i=1}^n\frac{i}{(n+1)^2(n+2)}\\ &=\frac{1}{n(n+1)^2(n+2)}\sum_{i=1}^n i\\ &=\frac{1}{2(n+1)(n+2)} \end{align*}

Therefore, $V\left[S_n\right]\to0$ as $n\to\infty$, which concludes the proof.

• If I am not mistaken, for bounded rv's this is a lot easier. In fact, (for convergence in probability) we need to prove that $\frac1n \sum_{k=1}^n\big(E[X_{(k)}]\big)^2 \to E[X^2]$. I don't see a good way to prove it for unbounded rv's. If you assume a lot, then there is no problem. – zhoraster Oct 20 '15 at 18:10
• Your assumption is that $\frac1{n}\sum_i X_{(i)}X^{\prime}_{(i)}\to\frac1{n}\sum_i E\left[X_{(i)}\right]E\left[X^{\prime}_{(i)}\right]$, but I do not understand why this is the case. Regarding the bounds of the rv, I am afraid that it will be as much difficult to extend this result to beta distributions as it will be for gamma distributions. – Louis-Claude Canon Oct 21 '15 at 8:21
• You've written it's quite sloppily (the "limit" depends on $n$), but yes, I mean this. And it is not an assumption, but a necessary and sufficient condition. I can write extended version of this comment if you want. – zhoraster Oct 21 '15 at 9:13
• Indeed, I use $\to$ as a short-cut for the convergence (in probability). I would have rather written the following. Since we know that $X_{(i)}\overset{\text{a.s.}}{\to}q_X(i/n)$ where $q_X(p)$ is the $p$-quantile of distribution $x$, then $\frac1{n}\sum_i X_{(i)}X^{\prime}_{(i)}\overset{\text{a.s.}}{\to}\frac1{n}\sum_i q_X(i/n)^2$, which is not exactly the same. My issue is that $E\left[X_{(i)}\right]\ne q_X(i/n)$ for a fixed $n$ and thus I am not sure we can say that $X_{(i)}\overset{\text{a.s.}}{\to}E\left[X_{(i)}\right]$. – Louis-Claude Canon Oct 21 '15 at 11:31
• I don't understand what you mean. For fixed $i$, $X_{(i)} \to \operatorname{ess\,inf} X$, $n\to\infty$. – zhoraster Oct 21 '15 at 15:10

This is not an answer, but too long for a comment.

In view of LLN, the convergence in probability $$\frac1n \sum_{i=1}^n X^{\vphantom{'}}_{(i)}X'_{(i)} \to E[X^2],\ n\to\infty, \tag{1}$$ is equivalent to $$\frac1n \sum_{i=1}^n\big(X^{2}_{(i)} + X'^2_{(i)} - 2X^{\vphantom{'}}_{(i)}X'_{(i)}\big) = \frac1n \sum_{i=1}^n\big(X^{\vphantom{'}}_{(i)}-X'_{(i)}\big)^2 \to 0,\ n\to \infty.$$

This is equivalent$^*$ to $$\frac1n \sum_{i=1}^n E\big[\big(X^{\vphantom{'}}_{(i)}-X'_{(i)}\big)^2\big] \to 0,\ n\to \infty.$$ But $$E\big[\big(X^{\vphantom{'}}_{(i)}-X'_{(i)}\big)^2\big] = V(X^{\vphantom{'}}_{(i)}-X'_{(i)}) = V(X^{\vphantom{'}}_{(i)})+V(X'_{(i)}) = 2V(X^{\vphantom{'}}_{(i)}) \\ = 2E[X^{2}_{(i)}] - 2\big(E[X^{\vphantom{'}}_{(i)}])^2.$$ Further, $$\frac{1}{n} \sum_{i=1}^n E[X^{2}_{(i)}] = E\left[\frac1n\sum_{i=1}^n X^{2}_{(i)}\right] = E\left[\frac1n\sum_{i=1}^n X^{2}_{i}\right] = E[X^2].$$

Therefore, $(1)$ is equivalent to $$\frac1n \sum_{i=1}^n \big(E[X^{\vphantom{'}}_{(i)}])^2 \to E[X^2],\ n\to\infty.$$

This seems easier than $(1)$ (since it is non-random) and can be proved e.g. for bounded rv's.

$^*$ $\Leftarrow$ is obvious. For $\Rightarrow$, write, using the rearrangement inequality, $$\frac1n \sum_{i=1}^n\big(X^{\vphantom{'}}_{(i)}-X'_{(i)}\big)^2 \le \frac1n \sum_{i=1}^n\big(X^{\vphantom{'}}_{i}-X'_{i}\big)^2 = \frac1n\sum_{i=1}^n Y_i,$$ where $Y_i$ are iid and integrable. Then it is not hard to show the uniform integrability (see e.g. here).

• If I understand correctly, the symbol $\to$ denotes the convergence in probability in (1) and the following formula, whereas it denotes the classical limit in what follows. And if the $\Leftarrow$ is obvious, this is because the $L^2$-convergence implies the convergence in probability. Thanks, this can be used to write a more concise proof for the uniform distribution. – Louis-Claude Canon Oct 23 '15 at 15:52
• If we consider the right-side of what remains to be proved, we can also say that $E\left[X^{2}\right]=\int_{-\infty}^{\infty}x^{2}f_{X}(x)dx=\int_{0}^{1}q_{X}(p)^{2}dp$ where $f_X(x)$ is the density function and $q_X(p)$ is the quantile function of distribution $X$ with the substitution $x=q_X(p)$. I am not sure, but this may also be equal to $\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n}q_{X}\left(\frac{i}{n}\right)^{2}$ (Riemann integral) if we assume that $f$ is integrable. We would thus have to show that this is equal to $\lim_{n\to\infty}\frac1{n}\sum_{i=1}^n E[X_{(i)}]^2$ (the left-side). – Louis-Claude Canon Oct 23 '15 at 16:15
• @Louis-ClaudeCanon, yes, this is how it is shown for bounded rv's. In fact, in this case you do not need the Riemann integrability of $f$, but only that of $q_X$, which is Riemann integrable thanks to monotonicity. – zhoraster Oct 23 '15 at 20:09