# 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 extra question. I am confused, why expectation does not depend on the permutations? Thank you for your explanations. –  Nick G.H. Apr 3 '12 at 6:02
@NickG.H.: I'm afraid I don't understand what you mean by "depend on the permutations". –  joriki Apr 3 '12 at 7:30
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
@NickG.H.: Sorry, even after deciphering your comment (please take a bit more care to avoid excessive typos; they're an unnecessary waste of the reader's time), I don't understand what you mean. The expectation value is taken over all possible permutations, so I don't see what it could mean for it to "depend on the permutations". I also don't understand what you mean when you say that you understand logically why but would like to find an explanation. If you already understand it, what would an explanation add? –  joriki Apr 3 '12 at 16:01