1
$\begingroup$

Let a be vector in $R^{2m}$.

I would like to calculate $E|\sum_{k=1}^ma_{\pi(k)}-\sum_{k=m+1}^{2m}a_{\pi(k)}|^2,$

Here $\pi(\cdot)$ is a permutation on the set{1,...,2m} with uniform distribution.

Thank you for the help.

2 Answers 2

1

The square contains the square of each entry once, which leads to a term $\lVert a\rVert^2$. It also contains $2m(m-1)$ positive and $2m^2$ negative terms with pairs of different entries, all of which get averaged to the same expectation value A, for a sum of $-2mA$. We can express this in terms of the variance of $a$:

$$ \begin{eqnarray} \def\Var{\operatorname{Var}}\Var a &=& \langle a_i^2\rangle-\langle a_i\rangle^2 \\ &=& \frac1{2m}\sum_ia_i^2-\frac1{(2m)^2}\left(\sum_ia_i\right)^2 \\ &=& \frac{2m-1}{(2m)^2}\sum_ia_i^2-\frac1{(2m)^2}\sum_{i\ne j}a_ia_j \\ &=& \frac{2m-1}{(2m)^2}\lVert a\rVert^2-\frac1{(2m)^2}2m(2m-1)A \\ &=& \frac{2m-1}{(2m)^2}\left(\lVert a\rVert^2-2mA\right) \end{eqnarray}$$

Thus your expectation value is $(2m)^2/(2m-1)$ times the variance of $a$.

  • 0
    Thank you very much for your help. I just don't see. Why terms are averaged to the same expected value. Could you please explein me. Thank you vary much2012-03-15
  • 0
    @Michael: You average over all permutations. That erases all distinctions between the entries. The only difference that still matters is whether a term is the product of two identical entries or two different entries. If it's the product of two different entries, the permutations will permute it into all possible pairs of different entries, and the number of permutations permuting it into a given pair will be the same for all pairs of different entries. If this isn't obvious, I suggest to try it out with a small number like $m=2$. And you're welcome :-).2012-03-15
  • 0
    Just for curiosity, is it possible to calculate the expectation $E|\sum_{k=1}^ma_{\pi(k)}-\sum_{k=m+1}^{2m}a_{\pi(k)}|$2012-07-29
  • 0
    @Michael: That seems difficult to do for general $a$, since the signs implied by the absolute value will depend on the relative magnitudes of the $a_i$.2012-07-29
1

The result is $$ \frac{2mB-A^2}{2m-1},\quad \text{with}\quad A=\sum_{k=1}^{2m}a_k\quad\text{and}\quad B=\sum_{k=1}^{2m}a_k^2. $$ To prove this, note that for every $k$ and every $\ell\ne k$, $$ \mathbb E(a_{\pi(k)}^2)=\frac{B}{2m},\quad\mathbb E(a_{\pi(k)}a_{\pi(\ell)})=\frac{A^2-B}{2m(m-1)}, $$ and expand the square in the expectation to be computed.

  • 0
    I think both $m$s in the first expression should be $2m$; that would avoid division by $0$ for $m=1$ and would make our results agree.2012-03-15
  • 0
    @did and joriki: Sorry for this question, I just wanted to make sure that I understand the calculations. I am considering now $E|\sum_{k=1}^ha_{\pi(k)}-\sum_{k=h+1}^{2m}a_{\pi(k)}|^2, 1\leq h \leq 2m $ and I got the same answer as in the post. Is it right?2012-09-12