MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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