# Summation Formula for Product of Two Distinct Integers within a Range (Derivation of Covariance)

I am trying to follow the derivation for the covariance of two discrete random variables. The joint distribution of the two random variables is known:

$$P(x=a, y=b) = \frac{1}{(m+n)(m+n-1)},$$ when $1 \leq a \leq m+n, 1 \leq b \leq m+n, a \neq b$.

The distribution of x is the same as y, and it is known:

$$P(x=a) = P(y=a) = \frac{1}{m+n},$$ when $1 \leq a \leq m+n$

Then, to calculate $Cov(x,y)$:

$$Cov(x,y) = E[xy] - E[x]E[y]$$ $$= \sum_{1 \leq a \leq m+n, 1 \leq b \leq m+n, a \neq b} \frac{ab}{(m+n)(m+n-1)} - \left(\frac{m+n+1}{2}\right)^2$$

The covariance is given as: $\displaystyle Cov(x,y) = -\frac{m+n+1}{12}$.

How do I express the summation in the covariance equation in terms of $m,n$? It is the product of two numbers, then varying the two numbers over a range, that is getting me stuck.

Thanks.

P.S. I have read the post here Variance for Summing over Distinct Random Integers, and I am getting stuck on step #3 of Didier Piau's post.

-
When you are getting stuck on a step of somebody's answer, a natural move would be to ask the guy directly, don't you think? – Did Jun 21 '11 at 6:44

First I'll write $N = m + n$, since $m$ and $n$ only ever appear in that combination. I assume that your difficulty is in computing

$$\sum_{1\leq a\leq N, 1\leq b\leq N, a\neq b} ab$$

One way to compute this is to include the terms where $a=b$ in the sum, and subtract them out afterward:

$$\sum_{1\leq a\leq N, 1\leq b\leq N} ab - \sum_{1\leq a=b\leq N} ab$$

Now you can do the two summations in the first term separately, and the second summation takes a simple form:

$$\left(\sum_{a=1}^N a\right) \left( \sum_{b=1}^N b\right) - \sum_{a=1}^N a^2$$

Now all you need are the formulas for the sum of the numbers from $1$ to $N$, and the sum of the squares from $1$ to $N$. These are given by:

$$\sum_{a=1}^N a = \frac{1}{2} N (N+1) \qquad \sum_{a=1}^N a^2 = \frac{1}{6}N(N+1)(2N+1)$$

and now you should be able to complete the calculation.

-
For the purpose of learning, using the above equations, the original question becomes the question of verifying: $\frac{\left(\frac12 N(N+1)\right)^2 - \frac16 N (N+1) (2N+1)}{N(N-1)} - \left(\frac{N+1}{2}\right)^2 = -\frac{N+1}{12}$. This can be verified by multiplying both sides by $N(N-1)$ and performing the necessary simplifications. – jrand Jun 15 '11 at 17:41

The following is a somewhat different approach, but it leads to calculations quite similar to those done by Chris Taylor. One disadvantage it has is that it is (maybe) trickier to visualize initially, somewhat more abstract. But it has the major advantage of introducing an important notion, that of conditional expectation. For a brief survey, one could start from here.

The conditional expectation of $XY$, given that $X=a$, is of course $a$ times the conditional expectation of $Y$, given $X=a$. In symbols, $$E(XY|(X=a))=aE(Y|(X=a))$$

To find $E(Y|(X=a))$, the obvious way is that given that $X=a$, you have $N-1$ possibilities for $Y$, all equally likely. So we want to add up all numbers from $1$ to $N$ except $a$, and divide by $N-1$. The required sum (before the division) is $N(N+1)/2-a$.

Now use the conditional expectation analogue of the usual way to get from conditional probabilities to probabilities. In this case, we get $$E(XY)= \sum_{a=1}^N E(XY|(X=a))P(X=a)$$

But $P(X=a)=1/N$. Now calculate. You still need to find the sum of the first $N$ numbers, and the sum of the first $N$ squares, so there is no computational advantage to this approach, in this case. Actually, if we let $\mu$ be the mean, the covariance is $E(X-\mu)(Y-\mu)$, we can use the same idea and save a lot of computation by noting cancellations. But it's kind of tricky, there is increased opportunity for error.

However, in many situations, conditional expectations are relatively easy to calculate, while the sums (or integrals) associated with calculating expectations directly from the definition, as you were doing, is a hopeless nightmare. So keep conditional expectations in mind!

-