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.
Explanation:
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}$
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.