Max Absolute Difference of Expectations under Change of Measure

Question

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.

Answer 1

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.