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
    @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
    @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