Colored Bins and Colored Balls

173 Views Asked by At

Suppose we have N different colors bins. Each bin can only hold B balls. Suppose we have N*B balls such that for each bin n we have B balls of the same color as this bin. Therefore in total we have N*B balls.

What is the probability that for a given bin I it contains a ball the same color as itself?

I got B/N*B = 1/N.

3

There are 3 best solutions below

1
On

Hint: First distribute the balls of color $A$, and then distribute the remaining balls. (This is exactly the same (probabilistically) as uniformly distributing all the balls at once).

The probability that bin $A$ \emph{does not} have a ball of color $A$ is the probability that all $A$ balls are distributed into the remaining $N-1$ bins. What is this probability?

3
On

Let's assume the balls of the same color are distinguishable (you may mark them black 1, black 2, ... black B etc). The difference between distinguishable and non-distinguishable does not matter much here. I just find it easier to explain in the distinguishable case and you may come up with a similar argument with the non-distinguishable case.

Another assumption is each ball configuration is equiprobable. There are all together $(NB)!$ configurations. Each such configuration has probability $\frac{1}{(NB)!}$

Suppose you have picked the bin A. Imagine you are filling this bin A first, and then the other bins. The number of ways to fill bin A will be $(NB)(NB-1)\cdots(NB-B+1)$. The number of ways to fill bin A without balls of the same color as bin A will be $(NB-B)(NB-B-1)\cdots(NB-2B+1)$. So the probability of filling bin A without balls of the same color as bin A is $\frac{(NB-B)(NB-B-1)\cdots(NB-2B+1)}{(NB)(NB-1)\cdots(NB-B+1)}$.

And the probability of filling bin A with at least one ball the same color as bin A is $1-\frac{(NB-B)(NB-B-1)\cdots(NB-2B+1)}{(NB)(NB-1)\cdots(NB-B+1)}$.

4
On

There are about $\frac {(NB)!}{(N!)^{B}(B!)^N}$ arrangements. First number all the balls. You can think of lining up all the balls, which gives $(NB)!$ possibilities. There are $N!$ ways to rearrange the balls within one bin and $B!$ ways to rearrange the balls of each color, giving equivalent distributions. It is not quite right because if two balls of the same color are in a bin we overcount the number of rearrangements.

The number of orders that do not have any balls of color $1$ in bin $1$ has the first $N$ factors of the numerator reduced by $N$ because we can't choose any balls of that color. The reduction is then a factor $$\frac {(NB-N)(NB-N-1)(NB-N-2)\ldots (NB-2N+1)}{(NB)(NB-1)(NB-2)\ldots (NB-N+1)}=\frac {(NB-N)!(NB-N)!}{(NB)!(NB-2N)!}$$ This is a job for Stirling's approximation, which makes it $$\frac {(NB-N)^{2(NB-N)}}{(NB)^{NB}(NB-2N)^{NB-2N}}\sqrt{\frac {(NB-N)(NB-N)}{(NB)(NB-2N)}}$$ The square root is very close to $1$ and I will ignore it. We can pull out all the $N$s and get $$\frac {(B-1)^{2(NB-N)}}{(B)^{NB}(B-2)^{NB-2N}}=\left(1-\frac 1{B-2}\right)^{NB}\left(1+\frac 1B\right)^{NB-2N}=\left(1-\frac 1{B-2}\right)^{2N}\left(1-\frac 2{B(B-2)}\right)^{NB-2N}$$