Say I have T balls, B of them black and T-B of them white.

I have N bins, each with a maximum capacity of T/N (that is, when the balls are all placed into the bins, all bins have the same number of balls, so assume T is always exactly divisible by N).

The balls are randomly assigned to the bins.

What is the probability that each of the bins has at least one black ball?

I figured out the probability that a given bin has a black ball, but I'm quite stuck at how to proceed - it doesn't seem that knowing the probability for a given bin helps me.


Consider the point of view of a black ball.

It can choose any of the $N$ bins. A bin does not have a black ball if it is not chosen by any of them, and probability that each of the bins does not have a black ball is the intersection $P(A_1\cap A_2\cap \dots A_N )$,

where $A_i$ is the event that bin $i$ does not have a black ball.

Since all $A_i$s are independent(balls choose bins independently randomly uniformly) this probability is the product of $P(A_i)'s$ which are each equal to $$1 - \Big(\frac{N-1}{N}\Big)^B$$ (bin not chosen by a particular black ball, do that for $B$ balls which gives to the power $B$, it's complement gives 'at last one black ball' case. Notice that this probability is independent of number of white balls)

Lastly, you should also subtract the probability of cases in which a bin is chosen by more than $\frac T{N}$ balls, as that is not possible.

  • $\begingroup$ Since the balls exactly fill the bins to capacity and all bins end up with the same number of balls, this calculation doesn't pertain to the case at hand -- you've shifted the entire work into the last sentence, subtracting out the inadmissible cases, i.e. almost all cases. $\endgroup$ – joriki Jun 7 '18 at 22:24

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.