Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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)$.

share|cite|improve this answer
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. – Michael Chernick Sep 18 '12 at 14:54
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.