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 $c \in R^N$. Let $c*=(c*_1,\ldots, c*_N)$ be non increasing rearrangement of $(|c_1|,\ldots,|c_N|)$. And let $r=(r_1,\ldots,r_N)$ be random variables, such that $P(r_i=1)=P(r_i=-1)=1/2$ and $\sum_{i=1}^N r_i=0$.

I wanted to compare $E|\sum_{i=1}^Nc_ir_i|$ and $E|\sum_{i=1}^Nc*_ir_i|$.

(I know that with independent random variables $r_i$, these two expectations are equal. But in our case we have dependence of $r_i$).

share|cite|improve this question
up vote 0 down vote accepted

The random variables $r_i$ are not independent, but the sequence $r_1,r_2,\dots ,r_N$ is exchangeable. That is, the random vectors $(r_1,r_2,\dots ,r_N)$ and $(r_{\pi(1)},r_{\pi(2)},\dots ,r_{\pi(N)})$ are identically distributed for any permutation $\pi$ on $\{1,2,\dots, N\}$. It follows that $\sum_{i=1}^Nc_ir_i$ and $\sum_{i=1}^Nc^*_ir_i$ are also identically distributed.

Added: In my solution, I assume that all of the $\pm 1$ vectors $r$ of length $N$ with $\sum_i r_i=0$ are equally likely. If you only assume that $P(r_i=1)=P(r_i=-1)=1/2$ and $\sum_i r_i=0$, then the result can be false.

For instance, when $N=4$ you could suppose that $r$ take the values $(+1,+1,-1,-1)$ and $(-1,-1,+1,+1)$ with probability $1/2$ each. Then $|\sum_{i=1}^Nc_ir_i|\equiv |(c_1+c_2)-(c_3+c_4)|$ and $|\sum_{i=1}^Nc^*_ir_i|\equiv |(c^*_1+c^*_2)-(c^*_3+c^*_4)|$ are degenerate random variables that need not take the same value.

share|cite|improve this answer
Thank you very much for your explanatin – David Apr 8 '12 at 17:39
Yes, this situation I ment before. Can we say something (in general) about relation between expectations in this situation? – David Apr 9 '12 at 0:42
In the situation that I added, you could end up with $E|\sum_{i=1}^Nc_ir_i|$ being less than, or equal to, or greater than $E|\sum_{i=1}^Nc^*_ir_i|$. You can't say anything in general. – Byron Schmuland Apr 9 '12 at 0:45

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.