3
$\begingroup$

I've the following question:

$k$ balls are thrown into $n$ bins, what is the probability that no bin is empty (all balls different)?

I know how to solve it when the balls are identical. In this case the answer is: $$Pr=\frac{\binom{k-1}{n-1}}{\binom{n+k-1}{n-1}}$$ I thought maybe to multiply the this answer by $k!$ because the balls are different but this will count also when the all swapped balls are swapped only by balls from the same bin. How to exclude this case from the counting with the multiplication?

$\endgroup$
17
  • 5
    $\begingroup$ Why do you think the fact that the balls are different will affect the probability that no bins are empty? The emptiness of a bin, or lack thereof, isn't affected by the label on a ball. $\endgroup$
    – Brian Tung
    Apr 21, 2017 at 14:50
  • $\begingroup$ @BrianTung Suppose I count the number of cases when no bin is empty with different balls. For some case there is also a case that I can swap between 2 balls from different bins. $\endgroup$ Apr 21, 2017 at 14:52
  • $\begingroup$ This is not clear. Give an example with small $k,n$ in which the distinctness of the balls changes the answer. $\endgroup$
    – lulu
    Apr 21, 2017 at 14:53
  • 1
    $\begingroup$ the probability that you want is the complementary to "at least one bin is empty". From this idea, and considering the probability that a ball fall in a bin uniform, the solution is straightforward. $\endgroup$
    – Masacroso
    Apr 21, 2017 at 14:59
  • 2
    $\begingroup$ Your example is not complete. Seems to me: If I have two bins and balls $a,b$ there are $4$ possibilities: $(ab,\emptyset),(\emptyset,ab),(a,b),(b,a)$ These are equiprobable so there is a $\frac 12$ probability that there is no empty bin. That's the same answer as if the balls were indistinguishable. $\endgroup$
    – lulu
    Apr 21, 2017 at 15:06

2 Answers 2

1
$\begingroup$

The presence or absence of labels on the balls does not affect the probability of a satisfactory arrangement (one in which no bin is empty). It increases the number of satisfactory arrangements, but the probability remains unchanged.

If that were not the case, our intuition would be awfully violated, because if you imagine a blindfolded person running this experiment with labelled balls, surely they cannot obtain a different result simply because they cannot see the balls!

To make this more concrete, suppose that you have $k = 2$ indistinguishable balls being placed in $n = 2$ urns. Neither bin is empty provided that neither bin has both balls. A bin has both balls with probability $\frac12 \times \frac12 = \frac14$. Since there are two bins, and it's impossible for both bins to have both balls, the probability that either bin has both balls is $\frac14+\frac14 = \frac12$, and the probability that neither bin is empty is therefore $1$ minus that, or $\frac12$.

Your commented that if the balls are distinguishable, there are four possibilities, while if the balls are indistinguishable, there are only three possibilities. That is only true if the bins are distinguishable, but you commented that they are not. So, in fact, there are only two possibilities whether the balls are distinguishable or not: Either the balls are in the same bin, or they are not. So shouldn't the probability be $\frac12$ either way?

Actually, such a line of reasoning would not be considered rigorous, either. The problem—as in your argument—is that we have not established that the possibilities have equal probability. It turns out that in this case, they do, but in your argument, the three possibilities—two balls in the first bin, two balls in the second bin, and a ball in each bin—are not equiprobable. The last possibility is twice as likely as the others. That can only happen if it has probability $\frac12$, and the other possibilities have probability $\frac14$. So you end up with the same answer after all.

Now, suppose the balls are distinguishable. You place ball $1$ into a bin; it doesn't matter which one. Then you place ball $2$ into a bin—do you place it into the same bin? If so (probability $\frac12$), the other bin is empty; if you don't (probability $\frac12$), neither bin is empty. So again, you obtain the probability $\frac12$.


If you accept the notion that labelling the balls does not affect the probability of any property that doesn't depend on the labels, and you know how to answer the question in the unlabelled case, then you should be able to apply that answer to the labelled case without modification. (However, your expression is wrong, again because you've treated the arrangements as equiprobable, when they are not. See here, for example, for the beginnings of an approach, applying inclusion-exclusion, that ends with callculus's result.)

$\endgroup$
2
  • $\begingroup$ However, your expression is wrong, again because you've treated the arrangements as equiprobable, when they are not - the arrangements are equiprobable in Bose-Einstein statistics. Unfortunately the problem has no compact solution in classical statistics. $\endgroup$
    – kludg
    Apr 21, 2017 at 18:09
  • $\begingroup$ @kludg: Yes, I've heard that. Though that's interesting, I think the OP is not likely to be thinking of that context. $\endgroup$
    – Brian Tung
    Apr 21, 2017 at 18:23
0
$\begingroup$

You can use the stirling number of the second kind. The number of ways to throw $k$ distinguishable balls into $n$ indistinguishable bins where no bin is empty is

$$ A(k,n)= S_{k,n}=\frac{1}{n!}\cdot \sum_{j=0}^n (-1)^{n-j} {n \choose j} j^k $$

The number of ways to throw $k$ distinguishable balls into $n$ indistinguishable bins with no condition is $$B(k,n)= \sum_{r=0}^n S_{k,r}=\sum_{r=0}^n\left(\frac{1}{r!}\cdot \sum_{j=0}^r (-1)^{r-j} {r \choose j} j^k \right) $$

Thus the required probability is $$\frac{\texttt{Number of favorable outcomes}}{\texttt{Number of possible outcomes }}=\frac{A(k,n)}{B(k,n)}$$

$\endgroup$

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.