I put $n\ge 2$ balls of various sizes into an urn. I draw two balls (without replacement) from the urn. With each draw, I draw any given ball with probability proportional to its size.

Can you show that the expected size of the first ball is at least the expected size of the second ball?

The expectations are easy to calculate. For $i\in[n]$, let $s_i>0$ be the size of ball $i$. Let $S=\sum_{i=1}^n s_i$ be the sum of the sizes. Then

  1. The expected size of the first ball is $~~~~~~~~~\displaystyle\sum_{i=1}^n \frac{s_i^2}{S}.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(i)$

  2. The expected size of the second ball is $~~~\displaystyle\sum_{i=1}^n \frac{s_i}{S} \Big(\sum_{j\ne i} \frac{s_j^2}{S-s_i}\Big).~~~~~~~(ii)$

You need to show (i) is at least as large as (ii). For $n=2$ it is easy to show.

Of course the inequality is tight if all balls are the same size.

For the case $n=3$, the inequality is equivalent to, for $a,b,c\ge 0$, $$a\frac{b^2+c^2}{b+c} + b\frac{a^2+c^2}{a+c} + c\frac{a^2+b^2}{a+b} \le a^2 + b^2 + c^2.$$



Answering my own question, for the record...

Let random variables $x_1$ and $x_2$ be the sizes of the first and second balls drawn, respectively. Let $F$ be the set containing the indices of the first two balls drawn. We want to show that $E[x_1 - x_2] \ge 0$.

To show it, it suffices to show that $E[x_1 - x_2~|~ F=\{i,j\}] \ge 0$ for any two balls $i$ and $j$.

By calculation, $E[x_1 - x_2 ~|~ F=\{i,j\}] \ge 0$ is equivalent to $$\frac{s_i}{S} \frac{s_j}{S-s_i}(s_i - s_j) ~+~\frac{s_j}{S} \frac{s_i}{S-s_j}(s_j - s_i) ~\ge~ 0.$$

(Recall $S$ is the sum of the sizes, so $s_i/S$ is the probability that $i$ is drawn first.)

Simplifying a bit, this reduces to the inequality $$- s_j(s_i-s_j) - s_i(s_j - s_i) ~\ge~ 0$$ which is equivalent to $$(s_i- s_j)(s_i-s_j) ~\ge~ 0,$$ which is true.


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.