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.



Max Absolute Difference of Expectations under Change of Measure
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.


