# Calculate the variance of $\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n S(X_i - X_j)$ for $X_1,\ldots,X_n$ i.i.d. random variables

In p.88 of Wand & Jones (1995), they asked to show the following result.

Let $$X_1,\ldots,X_n$$ be a set of i.i.d. random variables and define $$U=2n^{-2}\sum_{i=1}^{n-1} \sum_{j=i+1}^n S(X_i - X_j)$$ where the function $$S$$ is symmetric about zero. Show that \begin{align} \operatorname{Var}(U)= {} & 2n^{-3}(n-1) \operatorname{Var} \{S(X_1-X_2)\} \\ & {} +4n^{-3}(n-1)(n-2) \operatorname{Cov} \{S(X_1-X_2),S(X_2-X_3)\}. \end{align}

I've started with $$\operatorname{Var}(U)=4n^{-4}\sum_{i=1}^{n-1} \sum_{j=i+1}^n \sum_{l=1}^{n-1} \sum_{w=l+1}^n \operatorname{Cov}\{S(X_i-X_j),S(X_l-X_w)\}$$ and then isolating the case where $$l=i$$ and $$w=j$$, I could obtain the variance term

\begin{align} & \sum_{i=1}^{n-1} \sum_{j=i+1}^n \operatorname{Cov}\{S(X_i-X_j),S(X_i-X_j)\} \\[8pt] = {} & \left(\sum_{k=1}^{n-1}k\right) \operatorname{Var}\{S(X_1-X_2)\} \\[8pt] = {} & \frac{n(n-1)}{2} \operatorname{Var} \{S(X_1-X_2)\}, \end{align}

using the fact that the random variables are identically distributed.

I'm struggling to show the second term of $$\operatorname{Var}(U)$$, where the covariance appears. I would appreciate if someone could give me some advice.

**Update**


Let me be more specific. When I expand the covariance summations I get

\begin{align} 4^{-1}n^4 \operatorname{Var}(U) = {} & \sum_{i=1}^{n-1} \sum_{j>i}^n \operatorname{Var} \{S(X_i-X_j)\} \\ & {} + \sum_{i=1}^{n-2} \sum_{j>i}^n \sum_{w>i,w\neq j}^n \operatorname{Cov}\{S(X_i-X_j),S(X_i-X_w)\} \\ & {} +\sum_{i=1}^{n-1} \sum_{l\neq i,j>l}^{n-1} \sum_{j>i}^n \operatorname{Cov} \{S(X_i-X_j),S(X_l-X_j)\}, \end{align}

since $$\operatorname{Cov}\{S(X_i-X_j),S(X_l-X_w)\}=0,\forall i\neq l,j \neq w$$. And then using the identical distribution assumption, I obtained

\begin{align} 4^{-1}n^4 \operatorname{Var}(U)= {} & \frac{n(n-1)}{2} \operatorname{Var}\{S(X_1-X_2)\} \\[8pt] & {} + \frac{(n-2)(n-1)n}{3} \operatorname{Cov}\{S(X_1-X_2),S(X_1-X_3)\} \\[8pt] & {} + \frac{(n-2)(n-1)n}{3} \operatorname{Cov}\{S(X_1-X_2),S(X_3-X_2)\}. \end{align}

For each $$i, i=1,\ldots,n-2$$, I have $$(n-i)(n-i-1)$$ covariance possibilities of the form $$\operatorname{Cov}\{S(X_i-X_j),S(X_i-X_w)\},(j,w)>i,j\neq w$$, and then summing along $$i$$ gives $$\sum_{k=1}^{n-2}k(k+1)=\frac{(n-2)(n-1)n}{3}$$. Analogously, for each $$j, j=3,\ldots,n$$, I have $$(j-1)^2-(j-1)=(j-1)(j-2)$$ covariance possibilities of the form $$\operatorname{Cov}\{S(X_i-X_j),S(X_l-X_j)\},(i,l), and then summing along $$j$$ yields also $$\frac{(n-2)(n-1)n}{3}$$. Thus, if $$\operatorname{Cov}\{S(X_1-X_2),S(X_1-X_3)\}=\operatorname{Cov}\{S(X_1-X_2),S(X_2-X_3)\}$$, then

\begin{align} \operatorname{Var}(U) = {} & 2n^{-3}(n-1) \operatorname{Var}\{S(X_1-X_2)\} \\[6pt] & {} + \frac{8}{3} n^{-3} (n-1)(n-2) \operatorname{Cov}\{S(X_1-X_2),S(X_2-X_3)\}. \end{align}

Did I miss something?

• I don't see where those factors of $1/3$ come from. If you work out the result explicitly for the case $n=3$ (the sum is only three terms) the situation might become clearer. – whuber Jan 8 at 17:45
• For the case $Cov\{S(X_i-X_j),S(X_i-X_w)\},(j,w)>i,j\neq w$ suppose i=1, then we have $n-1$ different possibilities for $S(X_1-X_j)$, but for each of $S(X_1-X_j)$ we have $n-2$ different possibilities for $S(X_1-X_w)$ given that $w \neq j$. Thus for $i=1$ there are a total of $(n-1)(n-2)$ cases. If we sum along $i$, we have $(n-1)(n-2)+(n-2)(n-3)+...+2 = (n-2)(n-1)n/3$. – Danmat Jan 8 at 18:10
• Try it in the case $n=3$ to see what the correct factor is. – whuber Jan 8 at 18:12
• Thanks for your suggestion. I believe the calculations I just showed to you are valid for any $n$. By the way, I noticed something important. It is not true that $Cov\{S(X_i-X_j),S(X_l-X_w)\}=0,\forall i\neq l,j \neq w$, see for example $Cov\{S(X_5-X_{10}),S(X_2-X_5)\} \neq 0$, even though $i\neq l,j \neq w$. I was assuming it for the final formula. Maybe, this factor is missing in the coefficient of the covariance term. I will do the calculations now. – Danmat Jan 8 at 18:40
• @MichaelHardy You are right! I just realized this in the comment above. Thanks! – Danmat Jan 8 at 19:13

For the covariance term $$\operatorname{Cov}\{S(X_i-X_j),S(X_l-X_w)\}, j>i, w>l$$ the only zero cases occur when both $$l$$ and $$w$$ are different from $$i$$ and $$j$$.

Tedious decomposition of the summations gives \begin{align} 4^{-1}n^4 \operatorname{Var}(U) = {} & \sum_{i=1}^{n-1} \sum_{j>i}^n \operatorname{Var} \{S(X_i-X_j)\} \\ & {} + \sum_{i=1}^{n-2} \sum_{j>i}^n \sum_{w>i,w\neq j}^n \operatorname{Cov}\{S(X_i-X_j),S(X_i-X_w)\} \\ & {} +\sum_{i=1}^{n-1} \sum_{j>i}^n \sum_{l\neq i,j>l}^{n-1} \operatorname{Cov} \{S(X_i-X_j),S(X_l-X_j)\}\\ & {} +\sum_{i=1}^{n-1} \sum_{j>i}^{n} \sum_{w>j}^n \operatorname{Cov} \{S(X_i-X_j),S(X_j-X_w)\}\\ & {} +\sum_{i=1}^{n-1} \sum_{j>i}^{n} \sum_{i>l}^{n-1} \operatorname{Cov} \{S(X_i-X_j),S(X_l-X_i)\}\\ & {} +\sum_{i=1}^{n-1} \sum_{j>i}^{n} \sum_{l \neq i,l \neq j}^{n-1} \sum_{w>l,w \neq j, w \neq i}^n \operatorname{Cov} \{S(X_i-X_j),S(X_l-X_w)\} \end{align}

The assumption that $$X_1, \ldots,X_n$$ are a set of i.i.d random variables ensures that all the covariances above are the same, with the exception of the last term which is zero. Then, with a little of combinatorics, we obtain

\begin{align} 4^{-1}n^4 \operatorname{Var}(U) = {} & [(n-1)+(n-2)+\ldots+1] \operatorname{Var} \{S(X_1-X_2)\}\\ & {} +2[(n-1)(n-2)+(n-2)(n-3)+\ldots+2]\operatorname{Cov}\{S(X_1-X_2),S(X_2-X_3)\}\\ & {} +\frac{1}{2}[(n-1)(n-2)+(n-2)(n-3)+\ldots+2] \operatorname{Cov}\{S(X_1-X_2),S(X_2-X_3)\}\\ & {} +[(n-2)1+(n-3)2+\ldots+2(n-3)+1(n-2)] \operatorname{Cov}\{S(X_1-X_2),S(X_2-X_3)\}\\ \end{align}

Keeping in mind that $$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$$ and $$\sum_{k=1}^{n} k(k+1) = \frac{n(n+1)(n+2)}{3}$$, we easily see that $$\sum_{k=1}^{n-2} k(n-(k+1)) = \frac{n(n-1)(n-2)}{2}-\frac{n(n-1)(n-2)}{3}$$. Using these results, it is straightforward to obtain

\begin{align} 4^{-1}n^4 \operatorname{Var}(U) ={} & \frac{n(n-1)}{2}\operatorname{Var} \{S(X_1-X_2)\}\\ & {} +\frac{n(n-1)(n-2)}{3} \operatorname{Cov}\{S(X_1-X_2),S(X_2-X_3)\} \end{align}

which is the required result.

You have the right idea writing the variance as a sum of many covariances. Using iid-ness, you just need to separate that into two or three different kinds of sums that all have equal summands. Once you know all the summands are equal, you just need to count the number of times they show up.

If you look at the answer you want to end up with, it suggests there are two (or three) ways that you will get nonzero covariances. First $$\text{Cov}\left( S(X_i - X_j), S(X_l - X_m)\right) \neq 0$$ when $$i = l$$ *and* $$j = m$$. This you took into account already, so nice job.

However, there are also the situations when

1. $$i = l$$ *and* $$j \neq m$$
2. $$i \neq l$$ *and* $$j = m$$.

If either of these are true, then there is one $$X$$ random variable, not two, in each of the arguments of your $$\text{Cov}(\cdot, \cdot)$$ operator.

• I appreciate your comment. My problem is to count the number of times that these nonzero covariances appear. I've updated my question. Can you check if I did something wrong? It looks like I missed something. – Danmat Jan 8 at 16:53
• @Danmat here's a hint: for a variance term you need to pick two indices out of $n$, so there should be ${n \choose 2}$. For a nonvariance covariance term, you need to pick $3$, so that's... – Taylor Jan 8 at 19:03
• Yes! I'm working on it. I assumed zero covariances more than I meant to. Thanks! – Danmat Jan 8 at 19:12

You wrote: "since $$\operatorname{Cov}\{S(X_i-X_j),S(X_\ell-X_w)\}=0,\forall i\neq \ell,j \neq w$$."

That's wrong. In some terms you have $$i\ne\ell$$ and $$j\ne w$$ but $$\ell=j.$$ What happens then?

Suppose $$n=5$$ and $$(i,j)=(1,2)$$ and we forbid $$1=\ell$$ and $$2=j.$$ Then cases of nonzero covariance include: \begin{align} (\ell,w) = {} & \phantom{\text{or }} (2,3) \\ & \text{or } (2,4) \\ & \text{or } (2,5). \end{align} Now suppose $$n=5$$ and $$(i,j)=(4,5).$$ Then cases of nonzero covariance include \begin{align} (\ell,w) = & \phantom{\text{or }} (1,4) \\ & \text{or } (2,4) \\ & \text{or } (3,4). \end{align} and so on.