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

CC BY-SA 4.0
2019-05-24T22:39:34.583Z
You're right, missed that. Any thoughts on whether this is optimal?
R B
CC BY-SA 4.0
2019-05-25T20:58:03.150Z
@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
CC BY-SA 4.0
2019-05-24T22:33:48.777Z
2019-05-24T22:33:48.777Z
GMB
<p>Let <span class="math-container">$n,\ell\in\mathbb N$</span> for some <span class="math-container">$n\gg \ell\gg 1$</span>.</p>

<p>The goal is to pick two sequences of numbers, <span class="math-container">$x_1,\ldots,x_\ell$</span> and <span class="math-container">$y_1,\ldots,y_\ell$</span> such that <span class="math-container">$$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\quad{} \Sigma_{i=1}^\ell y_i = \ell\cdot n.$$</span></p>

<p>Next, there are <span class="math-container">$\ell$</span> bins such that bin <span class="math-container">$i$</span> contains <span class="math-container">$x_i$</span> blue balls. 
Given a random permutation <span class="math-container">$\sigma:[\ell]\to[\ell]$</span>, <span class="math-container">$y_{i}$</span> is the number of red balls in bin <span class="math-container">$\sigma(i)$</span>. </p>

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

<blockquote>
  <p><strong>How can we select <span class="math-container">$x,y$</span> to maximize our winning odds?</strong></p>
</blockquote>

<hr>

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

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

<p><em>Is this optimal?</em></p>

<p>Formulated as a math expression:</p>

<blockquote>
  <p>What is <span class="math-container">$\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]$</span>?</p>
</blockquote>

<co.combinatorics><pr.probability>
How to play the following game? (placing balls into bins)
R B
# How to play the following game? (placing balls into bins)

(Asked by: username_0 on 2019-05-24)

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

**Tags:** co.combinatorics, pr.probability

---

## 1 answers

### Answer by username_1 on 2019-05-24. Score: 1

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

> **Comments:**
> **username_0**: You're right, missed that. Any thoughts on whether this is optimal?  
> **username_1**: @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.  

---

