# 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
Commented Jan 8, 2019 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$. Commented Jan 8, 2019 at 18:10
• Try it in the case $n=3$ to see what the correct factor is.
– whuber
Commented Jan 8, 2019 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. Commented Jan 8, 2019 at 18:40
• @MichaelHardy You are right! I just realized this in the comment above. Thanks! Commented Jan 8, 2019 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. Commented Jan 8, 2019 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... Commented Jan 8, 2019 at 19:03
• Yes! I'm working on it. I assumed zero covariances more than I meant to. Thanks! Commented Jan 8, 2019 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.

Since the function $$S$$ is symmetric about $$0$$, if we denote $$S(x - y)$$ by $$\phi(x, y)$$, then the $$U$$ in your question can be viewed as a (scaled) U-statistic with the kernel $$\phi$$: \begin{align*} U = 2n^{-2}\binom{n}{2}\frac{1}{\binom{n}{2}}\sum_{1 \leq i < j \leq n}\phi(X_i, X_j) =: \frac{n - 1}{n}\tilde{U}. \tag{0}\label{0} \end{align*}

By doing so, we can apply the well-known variance formula for generic U-statistics directly to solving your problem. One such theorem is as follows (Elements of Large Sample Theory by E. Lehmann, Theorem 6.1.1):

The variance of the U-statistic \begin{align*} U = \frac{1}{\binom{n}{a}}\sum_{1 \leq i_1 < \cdots < i_a \leq n}\phi(X_{i_1}, \ldots, X_{i_a}) \end{align*} is equal to \begin{align*} \operatorname{Var}(U) = \frac{1}{\binom{n}{a}}\sum_{i = 1}^a\binom{a}{i}\binom{n - a}{a - i}\sigma_i^2 \tag{1}\label{1} \end{align*} with \begin{align*} & \sigma_i^2 = \operatorname{Var}(\phi_i(X_1, \ldots, X_i)), \\ & \phi_i(x_1, \ldots, x_i) = E[\phi(x_1, \ldots, x_i, X_{i + 1}, \ldots, X_a)]. \end{align*}

In your problem, $$a = 2$$, and by definition \begin{align*} \phi_1(x_1) = E[\phi(x_1, X_2)], \quad \phi_2(x_1, x_2) = E[\phi(x_1, x_2)] = \phi(x_1, x_2). \end{align*} It can be shown that (see Lemma 6.1.1, same reference as above): \begin{align*} \sigma_1^2 = \operatorname{Cov}(\phi(X_1, X_2), \phi(X_1, X_3)), \quad \sigma_2^2 = \operatorname{Var}(\phi(X_1, X_2)). \tag{2}\label{2} \end{align*}

Substituting $$\eqref{2}$$ into $$\eqref{1}$$ yields (treat $$\tilde{U}$$ as $$U$$ in the Theorem): \begin{align*} & \operatorname{Var}(\tilde{U}) = \frac{1}{\binom{n}{2}}\left[ 2\binom{n - 2}{2 - 1}\sigma_1^2 + \sigma_2^2\right] \\ =& \frac{4(n - 2)}{n(n - 1)}\operatorname{Cov}(S(X_1 - X_2), S(X_1 - X_3)) + \frac{2}{n(n - 1)}\operatorname{Var}(S(X_1 - X_2)). \tag{3}\label{3} \end{align*} Substituting $$\eqref{3}$$ into $$\eqref{0}$$ then yields \begin{align*} & \operatorname{Var}(U) = \frac{(n - 1)^2}{n^2}\operatorname{Var}(\tilde{U}) \\ =& \frac{4(n - 1)(n - 2)}{n^3}\operatorname{Cov}(S(X_1 - X_2), S(X_1 - X_3)) + \frac{2(n - 1)}{n^3}\operatorname{Var}(S(X_1 - X_2)), \end{align*} matching your final result.