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

Question

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)<j,l\neq i$, 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?

Thanks in advance.

Answer 1

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.

Answer 2

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.

Answer 3

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.