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

Let $x$ be vector in $R^n$. Let $\pi(⋅)$ be a permutation on the set $\{1,\ldots,n\}$ with a uniform distribution. Let $|m|\leq n, m \in Z$.

Calculate $$ E\left|\sum_{i=1}^mx_{\pi(i)}\right|^q, \quad q\geq 2. $$

Thank you.

share|cite|improve this question
There are $n!$ permutations, and $2^n$ subsets, of the set in question. The latter number is much smaller than the former, and still smaller is $\binom n m$, the number of subsets of size $m$. And you're really just choosing a random subset of size $m$ and working with that. It doesn't matter in which order you place the element within that subset or within its complement. But so far I don't really know if that helps. – Michael Hardy Jan 31 '13 at 3:47
Without the absolute value and the $q$th power, this would be really easy. – Michael Hardy Jan 31 '13 at 3:59
Thank you. Yes, I've been analusing this, but did not get any result. Is it possible at least to get a good bound from above? – Alex Jan 31 '13 at 4:03
up vote 0 down vote accepted

If $n\geqslant2$ and $q=2$, the result is $$ \frac{m(n-m)}{n(n-1)}\sum_{k=1}^nx_k^2+\frac{m(m-1)}{n(n-1)}\left(\sum_{k=1}^nx_k\right)^2. $$ A similar (but more tedious) expansion is possible for $q=4$ and more generally for every even integer $q$.

share|cite|improve this answer
Since I do not understand the condition $|m|\leqslant n$, this assumes that $0\leqslant m\leqslant n$. – Did Jan 31 '13 at 12:12
@Did: Thank you. Is there any possibility to approimate the $q$-th moment $E|\sum_{i=1}^mx_{\pi(i)}|^q$ using bernoulli (or maybe some other) distribution? Thank you. – Alex Feb 20 '13 at 16:46

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.