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.

  • $\begingroup$ Seems like a homework problem. You may have more luck posting this on math.stackexchange $\endgroup$ – Robert K Aug 20 '11 at 23:17
  • $\begingroup$ 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. $\endgroup$ – Yemon Choi Aug 20 '11 at 23:42
  • 1
    $\begingroup$ 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$. $\endgroup$ – hchen Aug 21 '11 at 2:45

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.

  • $\begingroup$ 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. $\endgroup$ – Brendan McKay Aug 21 '11 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.