# Covariance of order statistics

I'm a researcher in social science and I have encountered the following math formulation of a problem in my field. Note that I'm relatively new to stack exchange and I have already posted this on math.stackexchange as well as mathoverflow, before being asked to post it here. Please let me know if I should delete the double post from the sites (otherwise I will definitely update all sites when I receive an answer). Thank you!

Let $x_1,x_2,...,x_n,x_{n+1}$ be $n+1$ i.i.d. random variable with non-negative support and strictly positive probability mass around zero. Let $$z_k\equiv \min\{x_1,...,x_k\}.$$

In simulations, I find $Cov(z_{n+1},z_n)$ to be very close to $Var(z_{n+1})$ and very different from $Var(z_{n})$, as long as $n>>1$. I have tried this for many distributions (with non-negative support): $Cov(z_{n+1},z_n) / Var(z_{n+1}) \approx 1$ and the approximation gets better as $n$ increases, even for small $n$ such as $n=5$. On the other hand, $Cov(z_{n+1},z_n)/Var(z_n)$ is very far from 1.

How can I formalize this? That is, I'm looking for some kind of bounds on how the approximation improves with $n$. Of course, as $n\to\infty$, $Var(z_n)=Var(z_{n+1})$, so I'm looking for results either for $n$ finite, or an asymptotic result that takes $n$ to $\infty$ on $m\equiv floor(c\cdot n)$ for constant $c>1$ such that $Cov(z_n,z_m)$ is closer to $Var(z_m)$ than $Var(z_n)$.

Note that the approximation only works for X with non-negative support and has a positive probability mass in a neighborhood around zero. I believe that from results in extreme value theory, such distributions have exponential distribution in the limit. I don't know if this is important.

• If you wanted to analyze a specific example, taking the $x_i$ to be uniform might be convenient; the $z_i$ will then be $\beta$ distributions, which, among other things, have closed-form variances. If you're interested in the phenomenon across distributions more broadly, you may find the Fisher-Tippett-Gnedenko Theorem relevant – Bill Bradley May 22 '16 at 1:15
• Hi Bill, thanks for the response. Yes, I did derive the closed form solution for uniform, and verified my conjecture. I will check out the FTG theorem you cited. Thanks a lot. Just a quick question, before I dive into it: do you think (gut-feeling or otherwise) a more general result is possible, using FTG theorem, or are you citing it simply because my question is related to extreme value distributions? Thanks again. – user341296 May 22 '16 at 1:17
• Sorry, forgot to tag you - @BillBradley . Thanks again! – user341296 May 22 '16 at 3:33
• @wolfies answer is very nice, but to formalize it, one might want a general tool for characterizing the distribution of the gap between the first and second order statistics. The FTG at least lets you characterize the first order statistic across distributions quite broadly, so I was hoping it might be the right tool to apply. That's the extent of my "gut-feeling" :) – Bill Bradley May 23 '16 at 14:42

Let $(X_1,\dots,X_n,X_{n+1})$ denote a random sample of size $(n+1)$ drawn on $X$, and let $$Z_n = \min\{X_1,...,X_n\} \quad \text{and} \quad Z_{n+1} = \min\{X_1,...,X_n,X_{n+1}\}$$

By including the extra $X_{n+1}$ term, there are only 2 possibilities:

• EITHER CASE A $\rightarrow$ with probability $\frac{n}{n+1}$

$\quad \quad \text{The extra term } X_{n+1}$ does NOT change the sample minimum i.e. $z_{n+1} = z_n$. Then:

$$\text{Cov}(Z_n, Z_{n+1})\big|_\text{Case A} \; = \; \text{Cov}(Z_{n+1}, Z_{n+1}) \; = \; \text{Var}(Z_{n+1})$$

Since Event A occurs with probability $\frac{n}{n+1}$, this immediately explains why your observed unconditional covariance $\text{Cov}(Z_n, Z_{n+1})$ is well approximated by $\text{Var}(Z_{n+1})$, as $n$ increases.

• OR CASE B $\rightarrow$ with probability $\frac{1}{n+1}$

$\quad \quad \text{The extra term } X_{n+1}$ DOES change the sample minimum i.e. $Z_{n+1} < Z_n$. Then $Z_{n+1}$ and $Z_n$ must be the $1^{\text{st}}$ and $2^{\text{nd}}$ order statistics from a sample of size $n+1$ i.e.

$$\text{Cov}(Z_n, Z_{n+1})\big|_\text{Case B} \; = \; \text{Cov}\big(X_{(1)}, X_{(2)}\big) \text{ in a sample of size: } n+1$$

In summary:

\begin{align*}\displaystyle \text{Cov}(Z_n, Z_{n+1}) \; &= \frac{n}{n+1}\text{Cov}(Z_n, Z_{n+1})\big|_\text{Case A} \quad + \quad \frac{1}{n+1}\text{Cov}(Z_n, Z_{n+1})\big|_\text{Case B} \\ &= \frac{n}{n+1} \text{Var}(Z_{n+1}) \quad + \quad \frac{1}{n+1} \text{Cov}\big(X_{(1)}, X_{(2)}\big)_{\text{sample size } = n+1} \\ & \end{align*}

This makes it easy to see why the result is similar to $\text{Var}(Z_{n+1})$: because Case A dominates with probability $\frac{n}{n+1}$

Example and Check: Uniform Parent

In the case of $X \sim \text{Uniform}(0,1)$ parent:

• Case A: $\text{Var}(Z_{n+1}) = \text{Var}(X_{(1)})_{\text{sample size } = n+1} = \frac{n+1}{(n+2)^2 (n+3)}$

• Case B: $\text{Cov}\big(X_{(1)}, X_{(2)}\big)_{\text{sample size } = n+1} = \frac{n}{(n+2)^2 (n+3)}$

• Then: $\text{Cov}(Z_n, Z_{n+1}) = \frac{n}{(n+1) (n+2) (n+3)}$

The following diagram compares:

• this exact theoretical solution for $\text{Cov}(Z_n, Z_{n+1})$, as $n$ increases from 1 to 30 $\rightarrow$ the red curve

• to a Monte Carlo calculation of $\text{Cov}(Z_n, Z_{n+1})$ $\rightarrow$ the blue dots

Looks fine.

The following diagram compares the exact theoretical solution for $\text{Cov}(Z_n, Z_{n+1})$, $\text{Var}(Z_n)$ and $\text{Var}(Z_{n+1})$: as the OP reports, by the time $n = 5$, $\text{Cov}(Z_n, Z_{n+1})$ is well approximated by $\text{Var}(Z_{n+1})$:

• Hi wolfies, thanks a lot for typing this up. I have two small follow-up / clarification questions. 1) Your analysis for $Cov(Z_n,Z_{n+1}) \approx V(Z_{n+1})$ is compelling. Do you think it's possible to have a formal analysis to show that $Cov(Z_n, Z_{n+1})$ is closer to $V(Z_{n+1})$ than $V(Z_n)$, whatever "closer" means? 2) I understand that as we take $n$ to infinity, then $V(Z_n)=V(Z_{n+1})$. Do you think a similar result would hold asymptotically, i.e. let $m=floor(1.1*n)$, then can we have $Cov(Z_n,Z_m)\approx V(Z_m)$ and $Cov(Z_n,Z_m)\not\approx V(Z_n)$? Thanks a lot! – user341296 May 22 '16 at 19:46
• Actually, your arguments in case A applies similarly to $V(Z_n)$, that is, with probability $\frac{n}{n+1}$, $Z_n=Z_{n+1}$ and $V(Z_n)=V(Z_{n+1})$. Hence I do not think the answer explains why $Cov(Z_n,Z_{n+1})\approx V(Z_{n+1} \not\approx V(Z_n)$. – user341296 May 22 '16 at 19:52
• user341296 wrote: /////// "Under case A: $Z_n = Z_{n+1}$ so $Var(Z_n) = Var(Z_{n+1})$ //////////// No - that does not follow ... and it is the crux of the issue. Under Case A, $Var(Z_{n+1})$ denotes the variance of the sample min in a sample of size $n+1$. $Var(Z_{n})$ denotes the variance of the sample min in a sample of size $n$: even though $z_{n+1} = z_n$, the variance of the two variables is different. – wolfies May 22 '16 at 20:00
• Apologize for my rusty stats background, I don't immediately understand your comment about $V(Z_n)\neq V(Z_{n+1})$ yet but I'll think about it more. On the other hand, the approximation only works for X with non-negative support and has a positive probability mass in a neighborhood around zero. If you try simulation with normal distribution, you'll see that the approximation doesn't hold. I think your case A applies to those distributions as well, hence I still think I'm missing something... – user341296 May 22 '16 at 20:11
• Will need to give some thought to the 'correctness' of the $\frac{n}{n+1}$ bits, in non-Uniform cases. Time for bed ... back later :) – wolfies May 22 '16 at 20:35

This seems to imply that Var(zn)/Var(zn+1) if far from 1 as well. If zi is really the minimum of a sample of size i, then for standard computable examples, like the exponential distribution, the ratio of variances is close to 1 for n reasonably large, for example ((n+1)/n)^2 for the exponential. Perhaps you're simulating the second smallest order statistic?

• Hi kjetil, thanks for you answer. I understand that as $n$ grows to infinity, then $Var(Z_n) / Var(Z_{n+1})$ goes to 1. However, please see the second plot in the answer provided by @wolfies . Red curve is much closer to green than purple - that's what I'm trying to explain. – user341296 May 22 '16 at 19:54