Let c = $max_{j\in[m]}$ E[$C_j$], where $C_j$ = $\frac{1}{s_j} \sum_1^n w_i p_i^j$.
$C$ = E[$max_{j\in [m]} C_j$]
Two questions, first what is C. It sure looks like to me that we are just taking the expected value of of a constant. 2nd question: c $\leq C$. Why is this so? It's supposed to be obvious, but it is not to me. Is it always the case that the expected value of a max is >= the max of a expected value?
I'm trying to follow the argument here: http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/SODA-2002-Full.pdf on starting with equation (2).
This is easiest to see if you imagine a zero-mean process with a large variance. No matter how big the variance gets, the mean will still hang out around zero. Taking the max of the expected value is similar to asking how far the sample average strayed from the mean.
On the other hand, as the variance of our zero-mean process increases, the max values will also tend to increase. Taking the expected value of the max is similar to asking how far the farthest samples strayed from the mean on average.
This is a big simplification, but hopefully it gives some extra intuition. Also, I am an engineer, not a mathematician, so I apologize if my terminology is somewhat engineering-specific.