Max Absolute Difference of Expectations under Change of Measure Given a sample space $\Omega=\{ 1,\cdots,N \}$, a random variable $x$ defined on $\Omega$ that takes value $x_1,\cdots,x_N$, and a set of strictly positive real numbers $w_1,\cdots,w_N$. Define for any probability distribution $\lbrace p_i \rbrace$ on $\Omega$ another probability distribution $\{q_i\}$ as $q_i(\{ p_i \})=w_i p_i /\sum_k w_k p_k$. The question is what is the maximum absolute difference of expectations of x under p and under q, that is, 
$\max_p |\sum_i x_i p_i -\sum_i x_i \frac{w_i p_i}{\sum_k w_k p_k}|$
I guess that the maximum is 
$\max_{i,j} |(x_i-x_j)\frac{\sqrt{w_i}-\sqrt{w_j}}{\sqrt{w_i}+\sqrt{w_j}}|$
However I don't have any proof to know whether this is correct. Is this correct? This seems to be a fairly straight-forward problem and most likely has a known result. Please let me know how this is solved.
 A: By some continuity argument, we can assume that the weights $w_i$ are distinct.
Take any three indexes, say 1,2,3.
Increase $p_1$ by $\epsilon(w_3-w_2)$, $p_2$ by $\epsilon(w_1-w_3)$ and $p_3$ by
$\epsilon(w_2-w_1)$, where $\epsilon$ is tiny.  It is easily seen that this change does not effect $\sum_i p_i$ or $\sum_i w_i p_i$. Now we calculate that the change to
$$\sum_i x_i p_i -\sum_i x_i \frac{w_i p_i}{\sum_k w_k p_k}$$ is
$\epsilon\Delta(1,2,3)$ where
\begin{eqnarray}
\Delta(1,2,3) &=& (x_2-x_3)w_1+(x_3-x_1)w_2+(x_1-x_2)w_3 \\
   &&{} + \frac{(x_2-x_3)w_2w_3+(x_3-x_1)w_1w_3+(x_1-x_2)w_1w_2}{\sum_k w_k p_k}.
\end{eqnarray}
If $p_1,p_2,p_3$ are strictly between 0 and 1, and $\Delta(1,2,3)\ne 0$, we can use
some tiny $\epsilon$ to get a better solution. If $p_1,p_2,p_3$ are strictly between 0 and 1, and $\Delta(1,2,3)=0$, the objective value doesn't depend on $\epsilon$ so we can choose
$\epsilon$ to make one of $p_1,p_2,p_3$ equal to 0 or 1.
Using arbitrary $i,j,k$ instead of $1,2,3$, we see that for $N\ge 3$, at least one of each triple $\{p_i,p_j,p_k\}$ is 0.  Therefore there is a optimal point with at most two of the $p_i$s nonzero.  Now apply the bound for $N=2$ to finish it.
