# Bound for the variance

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.

-
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. – Cristian Sep 18 '12 at 5:52
@Cristian: Sorry, I am confused now how to use this ineuality here. Could you elaborate, please. Thank you. – Michael Sep 18 '12 at 6:02
$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|$ – Cristian Sep 18 '12 at 6:03
@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... – Michael Sep 18 '12 at 6:09

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)$.
@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$. – joriki Sep 18 '12 at 15:25