Autocorrelation summation identity

Let $X_t$ be a weakly stationary process with mean $\mu$ and autocovariance function $\gamma$.

How do I show that $$n^{-2}\sum_{i=1}^n \sum_{j=1}^n cov(X_i, X_j)$$ equals $$n^{-2} \sum_{i-j=-n}^n (n- |i-j|)\gamma(i-j)$$

Thanks

• The definitions of weakly stationary and autocovariance explain how $\text{Cov}(X_i,X_j)$ can be replaced by $\gamma(i-j)$ in the double sum and the rest is a matter of manipulating those sums to collect common terms. Where exactly in this process are you stuck? – whuber Sep 4 '14 at 18:26
• Write out a $n\times n$ covariance matrix (with entries $\operatorname{cov}(X_i, X_j)$) and replace each $\operatorname{cov}(X_i, X_j)$ by $\gamma(i-j)$. DO NOT use letters such as $i$ and $j$ in your matrix; the top left corner should have $\gamma(0)$ in it. Admire each diagonal in the matrix thus created. What is the length of each diagonal (there are $2n-1$ diagonals of varying lengths for you to consider)? What is the sum of the entries on each diagonal? – Dilip Sarwate Sep 4 '14 at 19:56

I like Dilip's suggestion to admire a matrix, so I will depict it first for the case $n=5$ as an example:
The double sum adds the entries in this table. There are $5$ ($=n$) values of $\gamma(0)$ along the diagonal, $4$ ($=n-1$) of both $\gamma(1)$ and $\gamma(-1)$ along the super- and sub-diagonal, and so on.
Notice that the arguments to $\gamma$ range from $1-n$ up through $n-1$: there are none with arguments $-n$ or $n$.
Another way to visualize a double sum is to set up two linear arrays, one for each set of indexes, and match all possible pairs with arrows. Here, the lower array depicts the collection of first indexes $X_i$ while the upper array depicts the second indexes $X_j$. Each arrow represents the covariance between the corresponding random variables. Weak stationarity implies the covariances of parallel arrows (from $i$ to $j$, $i+1$ to $j+1$, $i+2$ to $j+2$, etc.) are all the same, equal to $\gamma(i-j)$, as shown in the legend at right. (The color-coding is the same as for the matrix above.) The double sum is the sum over all arrows, of which (count them) there are $5$ ($=n$) with the value $\gamma(0)$, etc.