# Proving that the product of 2 samples, when sorted in order, converges to the variance of the population

I have a question regarding the average value of the pairwise product of 2 ordered samples that are drawn from a random variable, $X$, which in this case is zero-mean Gaussian ($X \sim N(0,\sigma_x)$).

Let $x_1, x_2, ... x_n$ be $n$ samples drawn from the random variable $X$. Let us put these samples in ascending order, and call the result: $x_{(1)}, x_{(2)}, ... x_{(n)}$.

Let's go ahead and do the same for a second sample of $n$ elements drawn from $X$. We'll call these $x'_{(1)}, x'_{(2)}, ... x'_{(n)}$

(So the two sets of samples are each, separately, in ascending order)

Empirically, I've noticed that:

$$\lim_{n \rightarrow \infty} \frac{1}{n} \sum_i^n x_{(i)}x'_{(i)} \rightarrow \sigma_x^2$$

I'm trying to prove this result. Does anyone have any suggestions? I've been looking at the literature for order statistics, but I can't seem to come up with an airtight proof.

(Note that if I hadn't sorted them in order, the pairwise product between the two samples would obviously converge to zero, since $X$ is zero-mean: $\lim_{n \rightarrow \infty} \frac{1}{n} \sum_i^n x_{i}x'_{i} \rightarrow 0$)

(I asked this question math exchange, but I think it is more suited to this stackexchange).

• Given zero mean, $\frac{1}{n}\sum_{i=1}^n x_i^2$ converges to the true variance as $n \rightarrow \infty$. It seems like the more samples you draw, the closer each sample in the first sorted list will become to its partner in the second sorted list: $|x_i - x_i'| \rightarrow 0$, so $x_i x_i' \rightarrow x_i^2$. Perhaps this could explain your observation. I haven't thought carefully enough about this to say whether your conjecture is true or not, but maybe this could be a place to start. – user20160 Feb 16 '17 at 8:24
• If true, one way to prove this might be to look at the distribution of the $k$th order statistic for $n$ iid samples from a zero-mean Gaussian. Proving (for all $k \in [1, n]$) that this distribution approaches a delta function (e.g. that its variance approaches 0) as $n \rightarrow \infty$ would imply that $|x_i - x_i'| \rightarrow 0$. – user20160 Feb 16 '17 at 9:50
• Thank you @user20160! This is very helpful. I'm looking at the distribution of the $k$th order statistic. It is: $f_{(k)}(x) = \frac{n!}{(k-1)!(n-k)!}f_X(x)(F(x))^{k-1}(1-F(x))^{n-k}$. I tried to integrate this to find the mean and variance, but I can't seem to find a closed way to carry out this integral. Do you have any suggestions for how to carry this out? Thanks. – Curious Student Feb 16 '17 at 20:11

It also holds that

$$\frac{1}{n} \sum_i^n x_{(i)}^2 \rightarrow_p \sigma_x^2,\;\;\; \frac{1}{n} \sum_i^n [x'_{(i)}]^2 \rightarrow_p \sigma_x^2$$

since the result holds for any permutation of the index and so also for the ordered one. Then

$$\frac{1}{n} \sum_i^n x_{(i)}^2 + \frac{1}{n} \sum_i^n [x'_{(i)}]^2 \rightarrow_p 2\sigma_x^2$$

$$\implies \frac{1}{n} \sum_i^n [x_{(i)}-x'_{(i)}]^2 + \frac{2}{n} \sum_i^n x_{(i)}x'_{(i)} \rightarrow_p 2\sigma_x^2$$

$$\implies \frac{1}{n} \sum_i^n x_{(i)}x'_{(i)}\rightarrow_p \sigma_x^2 - \frac{1}{2n} \sum_i^n [x_{(i)}-x'_{(i)}]^2$$

So in order for the result to hold we must show that

$$\frac{1}{2n} \sum_i^n [x_{(i)}-x'_{(i)}]^2 \rightarrow_p 0$$

which in turn requires to show that

$$x_{(i)}-x'_{(i)} \rightarrow_p 0$$

and so also in distribution and therefore that $E\big[x_{(i)}-x'_{(i)}\big]^2 =0$

This is what a comment suggested, by the way. Can you take it from here?

• Thank you so much! This is very clear reasoning. However, I am still having a hard time taking it from here. As I mentioned in response to the comments, I can't seem to find a closed way to carry out the integrals of the $k$th order distribution to find the mean and variance. Do you have any suggestions? Thanks – Curious Student Feb 16 '17 at 20:19
• @AbubakarAbid No need to do that, which anyway is usually infeasible. What you need to show, as the comment suggested, is that the distribution function itself of an order statistic (not the density function) approaches a constant as $n$ goes to infinity. This is easily shown for $X_{(1)}$ and $X_{(n)}$ for example. – Alecos Papadopoulos Feb 16 '17 at 20:47
• Thanks @Alecos, sorry I'm not sure I understand. Are you suggesting that I show that the CDF of $X_{(k)}$ approaches a step function (meaning that all of the probability density is concentrated at a single point)? That seems even harder than computing the variance. Could you please show me how you concluded that was the case for $X_{(1)}$ or $X_{(n)}$? – Curious Student Feb 16 '17 at 21:50
• @AbubakarAbid In fact it it really simple. For the extremes, we have $F_{(1)}(x) = 1- [1-F(x)]^n$ and $F_{(n)}(x) = [F(x)]^n$, where $F$ is the distribution function of the unordered variable. They obviously go to a constant when $n$ goes to infinity, don't they? For the intermediate order statistics, the distribution function is $$F_{(i)}(x) = \sum_{k=i}^n {n \choose k} [F(x)]^k\cdot [1-F(x)]^{n-k}$$ and with a little fiddling around you can show that this sum too converges to a constant (in the sense that it does not depend on $x$ at the limit). – Alecos Papadopoulos Feb 16 '17 at 22:16
• @AbubakarAbid By the way, your question makes for a very good textbook exercise. – Alecos Papadopoulos Feb 16 '17 at 22:33