Probability that all bins have at least one black ball?

Question

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.

Answer 1

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.

Answer 2

$c=T/N$ is the (uniform) capacity of the bins; $W=T-B$ is the number of white balls. It suffices to compute the complementary probability, which is that at least one of the $N$ bins contains only, which is exactly $c$, white balls. The balls are randomly assigned, so one can assign first the white balls and fill up the bins with the black balls (all to the same capacity) a posteriori. That means one needs only to consider the ways of partitioning $W$ balls into $N$ bins. I can only think of a recursive approach. After placing $w$ white balls, $0\le w\le W$, there are $f_0$ bins with no white balls, $f_1$ bins with one white ball etc. That state is written down as $0^{f_0}1^{f_1}\cdots$, the notation of weak partitions, where $\sum_{i\ge 0}f_i= N$, $\sum_{i\ge 0} if_i=w$. To each of these states a probability $p$ is assigned, and we are interested in the probability $\sum_{k\ge 1} p(0^. 1^. \cdots c^k)$ that one or more bins contain only white balls, once $w=W$. Initially, before a white ball is placed, $w=0$, the state is $0^N$, which means all bins are empty, and $p(0^N)=1$. Placement of an additional ball disperses a state $0^{f_0}1^{f_1}\cdots i^{f_i}(i+1)^{f_{i+1}}\cdots c^{f_c}$ to the states $0^{f_0}1^{f_1}\cdots i^{f_i-1}(i+1)^{f_{i+1}+1} \cdots c^{f_c}$; for every positive exponent $f_i\ge 1$, $i<c$ in the state with $w$ balls, the state with $w+1$ balls has one of the exponents transferred to the next higher index. One can visualize that with a Hasse diagram of a poset of the states, where the state $0^N$ is at level 0, and the states at level $w+1$ are all those that can be generated this way from the states at level $w$. A state of probablity $p$ contributes $p\times f_i/\sum_{j<c} f_j$ to the state at the next level, because there are $f_i$ bins that could be receiving the next ball out of a total of $\sum_{j<c} f_j$. A recursive program of that kind can also solve What is the probability that throwing $m$ balls at random in $n$ urns at least one urn contains $c$ elements? .