Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

Please help me to understand the solution. I have two questions:

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?

Thank you for your explanations.

share|cite|improve this question
up vote 0 down vote accepted

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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.