4
$\begingroup$

I am trying to show that the second moment is bounded by 1 from above.

Let $x=(x_1, \ldots, x_n)$ be real vector such that $\|x\|_2=1$. Let $\pi(\cdot)$ be a permutation on the set $\{1,...,n\}$ with a uniform distribution. I would like to show that $E\left|\sum_{i=1}^kx_{\pi(i)}-\sum_{i=k+1}^{n}x_{\pi(i)}\right|^2\leq 1,$ $1\leq k\leq n$. $ $

As was shown in Expectation of the difference of sums

Denoting by $A=\sum_{i=1}^{n}x_i\quad\text{and}\quad B=\sum_{i=1}^{n}x_i^2$ we get that for every $i$ and every $i\ne j$, $ \mathbb E(x_{\pi(i)}^2)=\frac{B}{n},\quad\mathbb E(x_{\pi(i)}x_{\pi(j)})=\frac{A^2-B}{n(n-1)}. $

Now, expanding the square in the expectation, we obtain: $ E\left|\sum_{i=1}^kx_{\pi(i)}-\sum_{i=k+1}^{n}x_{\pi(i)}\right|^2=B+\frac{(A^2-B)(k(k-1)+(n-k)(n-k-1)-2kn)}{n(n-1)}. $

But now I am stuck. How do I show that the last expression is less than or equal to one?

Thank you.

  • 0
    @Cristian: Thsnk you. I understand now your idea. Its very hard to calculate an expectation of this function. And, unfortunately, I even have no idea how to bound an expectation...2012-09-18

1 Answers 1

1

This is false. For $k=n$, the value doesn't depend on $\pi$ and is simply $|\sum_ix_i|^2$, which is not necessarily $\le1$, e.g. for $x=(1/2,1/2,1/2,1/2)$.

  • 0
    @Michael: Yes, that would make sense; but the statement would still be false, since for the constant vector with components $1/\sqrt n$ the value is $|n-2k|/\sqrt n$ independent of $\pi$, and this can be $\gt1$.2012-09-18