Consider two bins that contain an unknown number of black balls.

We wish to split $n$ red balls (i.e., choose a number $x\in\{0,\ldots,n-1\}$ to place in a random bin) so that if we pick one ball at random from each bin we maximize our chances of sampling only red balls.

It seems that regardless of the number of black balls in each, we should split the red balls evenly.

Mathematically, show that for any positive numbers $b_1,b_2$ (representing the black balls) and $n$:

$$ \frac{x}{x+b_1}\cdot\frac{(n-x)}{(n-x)+b_2} + \frac{x}{x+b_2}\cdot\frac{(n-x)}{(n-x)+b_1} \le \frac{2\cdot (n/2)^2}{(n/2+b_1)\cdot (n/2+b_2)}. $$

One way to do that is to consider the function $f(x)$ $$ f(x) = \frac{x}{x+b_1}\cdot\frac{(n-x)}{(n-x)+b_2} + \frac{x}{x+b_2}\cdot\frac{(n-x)}{(n-x)+b_1}, $$ derive it, and find its maximum.

I'm wondering if there's some averaging argument that we can use to simplify this proof.

Clarification: Our goal is to choose the split $(x,n-x)$. We cannot determine whether $x$ will be in the bin with $b_1$ balls or the one with $b_2$ balls since we do not know $b_1$ and $b_2$. Therefore, I assume that $x$ will be placed with $b_1$ with prob. 1/2 and with $b_2$ with prob. 1/2.

  • $\begingroup$ Is $n $ assumed to be even? $\endgroup$ – user Jun 3 at 20:19
  • $\begingroup$ @user, sure, let's assume that. $\endgroup$ – R B Jun 3 at 20:20
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – robjohn Jun 4 at 12:38

Your Answer

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

Browse other questions tagged or ask your own question.