Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.