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
    what about using the Cauchy–Schwarz inequality? Perhaps you can show (hopefully it is easier too) that $E\left|\sum_{i=1}^{k}x_{\pi(i)}-\sum_{i=k+1}^{n}x_{\pi(i)}\right|$ is bounded above by one.2012-09-18
  • 0
    @Cristian: Sorry, I am confused now how to use this ineuality here. Could you elaborate, please. Thank you.2012-09-18
  • 0
    $E\left|\sum_{i=1}^kx_{\pi(i)}- \sum_{i=k+1}^{n}x_{\pi(i)}\right|^2\leq E\left|\sum_{i=1}^kx_{\pi(i)}-\sum_{i=k+1}^{n}x_{\pi(i)}\right|E\left|\sum_{i=1}^kx_{\pi(i)}-\sum_{i=k+1}^{n}x_{\pi(i)}\right|$2012-09-18
  • 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)$.

  • 1
    Since the second term in the expression under the absolute value sign runs from k+1 to n, I suspect that the OP intended k to run from 1 to n-1 only.2012-09-18
  • 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