# 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.

-
Seems like a homework problem. You may have more luck posting this on math.stackexchange –  Robert K Aug 20 '11 at 23:17
I am not so sure it is a homework problem, though it would help if the OP could give some justification for why his/her guess for the maximum has the form it does. –  Yemon Choi Aug 20 '11 at 23:42
No unfortunately it's not a homework problem, though I certainly wish it is so that I may find the solution much quicker :) The reason for the guess is that it is true for $N=2$ and for general $N$, it seems that $p-q(p)$ is contained in a polytope whose vertex set is like follows, $v_i=\frac{\sqrt{w_j}-\sqrt{w_i}}{\sqrt{w_i}+\sqrt{w_j}}$, $v_j=\frac{\sqrt{w_i}-\sqrt{w_j}}{\sqrt{w_i}+\sqrt{w_j}}$ for some pair $(i,j)$ and $v_k=0$ for all $k\ne i$ and $k\ne j$. –  hchen Aug 21 '11 at 2:45

## 1 Answer

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.

-
If there is a problem with the "continuity argument" in the first line, an alternate is to combine items with the same weight into a single item with the sum of the weights. This just reduces the dimension of the problem so it seems harmless. –  Brendan McKay Aug 21 '11 at 13:43