# How to play the following game? (placing balls into bins)

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]$$?

## 1 Answer

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$$.

• You're right, missed that. Any thoughts on whether this is optimal?
– R B
Commented May 24, 2019 at 22:39
• @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.
– GMB
Commented May 25, 2019 at 20:58