1
$\begingroup$

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

1 Answers 1

0

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.

  • 0
    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.2012-04-09