# Covariance of INID order statistics

In the IID case, it is known that all order statistics are positively correlated.* Thus, we know that $$\text{Cov}(X_{(i)},X_{(j)}) \geq 0.$$ Is this known in the INID (independent, non-identically distributed) case? If it is not known, how could this be proved? If it does not seem true, what would be a counter-example?

• E.g., see Bickel (1967), "Some contributions to the theory of order statistics"

It is known. We can even make a more precise and slightly stronger statement.

The following demonstration rests on two ideas. The first is that for any random variable $X$, the conditional expectation

$$\mathbb{E}[X | X \le t]$$

is a non-decreasing function of $t$. This is geometrically obvious: as $t$ increases, the integral extends over a region that is widening to the right, thereby shifting the expectation to the right.

The second idea concerns any joint random variables $(X,Y)$. A general way to study their relationship is to "slice" $X$ and study the average value of $Y$ within each slice. More formally, we can consider the conditional expectations

$$\nu(x) = \mathbb{E}[Y | X=x]$$

as a function of $x$. This function contains more information than the sign of the covariance or correlation, which only tells us whether this function increases or decreases on average. In particular, if $\nu$ is nondecreasing, then $\text{Cov}(X,Y) \ge 0$. (The converse is not true, which is why non-decrease of $\nu$ is a stronger condition than a non-negative covariance.)

To apply these ideas, let $X_{(i)}, 1\le i \le n,$ be order statistics for $n$ independent (but not necessarily identically distributed) random variables. Pick $1 \le i \lt j \le n$ for further study. Because $X_{(i)}\le X_{(j)}$ (by their very definition), the condition $X_{(i)} \le X_{(j)} | X_{(j)} = t$ is equivalent to $X_{(i)} | X_{(i)} \le t$. The first idea now informs us that the expected value of $X_{(i)} | X_{(j)}$ is nondecreasing with respect to the value of $X_{(j)}$. Letting $X_{(i)}$ play the role of $X$ and $X_{(j)}$ the role of $Y$ in the second idea implies $\text{Cov}(X_{(i)}, X_{(j)}) \ge 0$, QED.

(It is possible for such covariances to equal zero. This will happen whenever the variables have no overlaps in their ranges, for instance, for then the order statistics coincide with the variables, whence they are independent, whence all their covariances must vanish.)

An imperfect illustration of these ideas is afforded by a simulation in which the sampling is repeated thousands of times and a scatterplot matrix is drawn showing the $(X_{(i)}, X_{(j)})$ pairs. These scatterplots approximate the true bivariate distributions of the order statistics. The preceding demonstration asserts that all reasonable smooths of the scatterplots in the lower diagonal of the matrix will be non-decreasing curves. (They may fail to do so due to a few outlying or high-leverage points: this is just the luck of the draw, not a counterexample!)

For instance, I simulated data that were drawn independently from a uniform distribution, a Gamma(3,2) distribution, another uniform distribution supported on [1,2], a J-shaped Beta distribution (Beta(1/10, 3)), and a Normal distribution (N(1/2, 1)). Here are the results after 5,000 samples were drawn:

Sure enough, all the smooths (red curves) are nondecreasing. (Well, there's a high-leverage point at the left in the X.1 vs X.2 plot that makes it look like the smooth might initially decrease slightly, but that's an artifact of this finite sample. That's why I characterized this simulation as an "imperfect" illustration.)

The R code to reproduce this figure follows.

n.data <- 5000
rvs <- c(runif,
function(n) rgamma(n, shape=3, rate=2),
function(n) runif(n, 1, 2),
function(n) rbeta(n, .1, 3),
function(n) rnorm(n, 1/2))
set.seed(17)
x <- data.frame(t(apply(sapply(rvs, function(f) f(n.data)), 1, sort)))
names(x) <- c("X.1", "X.2", "X.3", "X.4", "X.5")
panel.smooth <- function(x, y, ...) {
points(x,y, ...)
lines(lowess(x,y, f=.9), col="Red", lwd=2)
}
pairs(x, lower.panel=panel.smooth, cex=0.5, col="Gray")