1
$\begingroup$

Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$.

The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\quad{} \Sigma_{i=1}^\ell y_i = \ell\cdot n.$$

Next, there are $\ell$ bins such that bin $i$ contains $x_i$ blue balls. Given a random permutation $\sigma:[\ell]\to[\ell]$, $y_{i}$ is the number of red balls in bin $\sigma(i)$.

From every non-empty bin, a random ball is chosen uniformly, and we win the game if all sampled balls are red.

How can we select $x,y$ to maximize our winning odds?


If we pick $x_1,\ldots,x_\ell=n/\ell$ and $y_1,\ldots,y_\ell=n$, we have that in each bin a red ball will be sampled with probability $1-1/(\ell+1)$ and the chance of getting only red balls would be $(1-1/(\ell+1))^{\ell}\approx 1/e$.

As GMB answered, it's possible to improve this by setting $x_1=\ldots=x_{\ell-1}=0$ and $x_\ell=y_1=\ldots=y_\ell=n$, and getting a success probablity of 1/2.

Is this optimal?

Formulated as a math expression:

What is $\max_{x,y\mid \Sigma_{i=1}^\ell x_i = n, \Sigma_{i=1}^\ell y_i = \ell\cdot n} \quad{} \mathbb E_\sigma\; \left[\prod_{i=1}^\ell \frac{y_{\sigma^{-1}(i)}}{y_{\sigma^{-1}(i)}+x_i}\right]$?

$\endgroup$
1
$\begingroup$

I think $x_1 = \dots = x_{\ell-1} = 0, x_{\ell} = y_1 = \dots = y_{\ell} = n$ is better. You are guaranteed to choose red in all bins except for bin $\ell$, and bin $\ell$ has $n$ red balls and $n$ blue balls, so your overall odds of success are $1/2 > 1/e$.

$\endgroup$
  • $\begingroup$ You're right, missed that. Any thoughts on whether this is optimal? $\endgroup$ – R B May 24 at 22:39
  • $\begingroup$ @RB I would guess that it is. I don't have a formal proof, but some very sketchy calculations suggest that you can always improve a solution by moving a ball from one bin to another if it increases the variance in the x's or decreases the variance in the y's. So this solution would be the only unimprovable one. $\endgroup$ – GMB May 25 at 20:58

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.