There are C containers, B black balls and infinite number of white balls. Each container should have at least one ball. Each of the containers may contain any number of black and white balls.

Action A: Chose any of the containers randomly and pick out one ball at random.

The probability that the outcome of the Action A is a white ball is greater than or equal to P. Describe the optimal algorithm to find the minimum number of white balls required to achieve this.


num_containers = 2, num_black_balls = 1, P = 60.

In this case putting a single white ball in one box and white+black in the other gives us 0.5 * 100% + 0.5 * 50% = 75% >= 60%

Output: 2 (minimum number of white balls required)

My attempt at a solution:

I keep track of how many black balls still need to be placed. I try to place them one by one in each of the possible C containers. If the probability of drawing a white ball after action A falls below P, I choose the container with "maximum gain" and place a white ball in it. I keep on placing the white balls until the probability of getting a white ball after action A becomes >= P.

Gain(Container i) = $\frac{w_i + 1}{w_i + 1 + b_i} - \frac{w_i}{w_i + b_i}$

  • $\begingroup$ This depends very much on how many balls has each container, not only on the number of white balls. Do you mean that this probability must be greater than or equal to $p$ under any distribution of the balls? $\endgroup$ – ajotatxe Oct 23 '14 at 16:54
  • $\begingroup$ What're your thoughts? I hope it's not your homework or even from an ongoing competition that we're seeing them these days very often! $\endgroup$ – Ehsan M. Kermani Oct 23 '14 at 16:56
  • $\begingroup$ @EhsanM.Kermani I have added my thoughts about solving the problem. Its not homework or any competition. You may take as much time as you like to share your thought process on it. Any help is appreciated without any limitations of time. $\endgroup$ – ibp73 Oct 23 '14 at 17:39
  • $\begingroup$ @ajotatxe You are free to distribute the balls amongst the containers. The probability must be greater than or equal to P for your chosen distribution. The goal is to minimize the number of white balls. $\endgroup$ – ibp73 Oct 23 '14 at 17:42

If $\frac {r-1}C<P\le \frac rC$ with $0\le r\le C-1$, it suffices to put a white ball into each of $r$ containers, and distribute the black balls only in the others (provided $B\ge C-r$); If $B<C-r$, we need $C-B$ white balls, obviously. The cost of this is: $\max\{r,C-B\}$ white balls.

With $C$ white balls, the best $P$ we can achieve is $1-\frac1C+\frac1C\frac1{B+1}=1-\frac{B}{(B+1)C}$: If any container has only black balls, this makes $P\le 1-\frac1C$, hence each container has at least one white ball, hence exactly one white ball. Then the task is to maximize $\frac1{b_1+1}+\ldots +\frac1{b_C+1}$ subject to $b_1+\ldots +b_C=B$. The maximum is achieved at the boundary, i.e. for example with $b_1=B, b_2=\ldots =b_C=0$, in which case indeed $1-\frac{B}{(B+1)C}$ is obtained. We conclude: For $1-\frac1C< P\le 1-\frac{B}{(B+1)C}$, the cost is $C$ white balls and for larger $P$ we need more than $C$ white balls.

With more white balls, it may be advisable to distribute the black balls among several containers. Considereing only two containers, we want to maximize $\frac{w_1}{w_1+b_1}+\frac{w_2}{w_2+b_2}$ subject to $b_1+b_2=\text{const}$. If ever the gain from the decreasing $b_1$, say, by $1$ outweighs the loss from increasing $b_2$ by $1$, then the outweighing is even stronger if $b_1$ is decreased/$b_2$ increased even further, thus we conclude that the best distribution is again with all black balls in one container, and all other containers containing only one white ball.

This leads us to the general bound: With $W\ge C-1$ white balls, the maximal achievable $P$ is $1-\frac1C+\frac1C\frac{W-C+1}{B+W-C+1}=1-\frac{B}{C(W+B+1-C)}$.

Conclusion: In the other direction, to obtain a success probability of at least $P$, one needs at least $$W=\begin{cases} \max\{C-B,\lceil PC\rceil\}&\text{if $P\le 1-\frac1C$}\\ \left\lceil\frac B{(1-P)C}\right \rceil+C-B-1 &\text{if $P>1-\frac1C$}\end{cases}$$ white balls.

| cite | improve this answer | |

I'm assuming that one may place balls in the containers however one chooses before Action A.

Hint: If $P=\frac{n}{C}$ for some integer $n$, you only require $n$ white balls (and this is indeed the minimum).

| cite | improve this answer | |

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.