0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ From what I gather, the total combinations must be B*N! / B!^{N}. Also, if A balls are distributed into the remaining N-1 bins, then we have (B*(N-1) choose B)(B*(N-1)! / B!^{N-1}) ways of doing this. Am I on the right track here? $\endgroup$ – J. Doe Sep 19 '18 at 5:13
0
$\begingroup$

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)}$.

$\endgroup$
  • $\begingroup$ To make it even more explicit, let's say bin A is Red. There are all together $(NB)!$ configurations. The number of configurations without any Red balls in bin A is $[(NB-B)\cdots(NB-2B+1)]\ [(NB-B)!]$. The first part, $[(NB-B)\cdots(NB-2B+1)]$, is the number of ways to fill the $B$ positions of bin A with the $NB-B$ non-Red balls. The second part, $(NB-B)!$, is the number of ways to fill all other bins with the remaining $NB-B$ balls. So the probability is given by $\frac{[(NB-B)\cdots(NB-2B+1)]\ [(NB-B)!]}{(NB)!} = \frac{(NB-B)\cdots(NB-2B+1)}{(NB)\cdots(NB-B+1)}$. $\endgroup$ – William Wong Sep 19 '18 at 6:07
  • $\begingroup$ What if N= 1 and B = 2? Then your formula gives undefined value. $\endgroup$ – J. Doe Sep 20 '18 at 14:36
  • $\begingroup$ Whenever N=1 (and whatever B is), you take that a special case. The probability of filling bin A with same color ball is just 1. $\endgroup$ – William Wong Sep 20 '18 at 17:46
0
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ That the balls are non-distinguishable does not matter much, so long as you follow through the deviation. For non-distinguishable balls, the totally number of arrangements is $\frac{(NB)!}{(B!)^N}$ (not $\frac{(NB)!}{(N!)^{2B}}$ as you mentioned above). But the same factor $(B!)^N$ has to be applied to the numerator when you compute the probability, so it just cancel out, and you will have the same final answer. $\endgroup$ – William Wong Sep 19 '18 at 5:56
  • $\begingroup$ @WilliamWong: I think the denominator should be $(B!)^N(N!)^B$ because of the two reorders I mention. I agree it doesn't factor into the second paragraph and on. $\endgroup$ – Ross Millikan Sep 19 '18 at 13:52
  • $\begingroup$ Ross, what if N = 1 and B = 2? Your formula gives an undefined value. $\endgroup$ – J. Doe Sep 20 '18 at 12:56
  • $\begingroup$ @J.Doe: Stirling's approximation assumes the number you are taking the factorial of is large. It is already good at $4$, where it returns $23.5$ compared to $24$, but below that is not so good. If there is only one bin, the probability is $0$ $\endgroup$ – Ross Millikan Sep 20 '18 at 15:15

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.