# understanding the solution for “Expectation of the difference of sums”

I found the question Expectation of the difference of sums on this site, and I am trying to understand the solution, which uses the variance of the vector $a$.

First, on the 4-th row of the solution, $$\begin{eqnarray} \def\Var{\operatorname{Var}}\Var a &=& \frac{2m-1}{(2m)^2}\lVert a\rVert^2-\frac1{(2m)^2}2m(2m-1)A\;, \end{eqnarray}$$ how did we get $2m(2m-1)$? (As I understand, we have $2m(m-1)$positive terms of different entries.)

My second question is how to find $A$, the average over all permutations?

-

On your first question: It seems your $2m(m-1)$ is the count of positive terms with pairs of different entries in the desired expectation value that I mention in the second line of the solution. This is a different count. The factor $2m(2m-1)$ counts the number of pairs of different entries in the sum $\sum_{i\ne j}a_ia_k$. There's no division of the vector into two halves with different signs here; we're merely counting pairs of entries of the entire vector to calculate the variance of the entire vector, so all $2m$ entries are treated the same, and there are $2m(2m-1)$ ordered pairs of different entries. This is just $n(n-1)$ with $n=2m$.
On your second question, $A$ is indeed the average over all permutations, but the point is that to average the product of a pair of different entries over all permutations, you don't have to actually go through all permutations, because you get the same result by just averaging over all pairs of different entries. So for $m=2$, A would be $(a_1a_2+a_1a_3+a_1a_4+a_2a_3+a_2a_4+a_3a_4)/6$.
Sorry, for rxample, $Ea^2_{\pi(i)}=\frac{\|a\|^2}{2m}$-tgere is no permutation in the RHS. I am anderstand logically why, but I would like to find explonation. Thank you – Nick G.H. Apr 3 '12 at 15:32