4
$\begingroup$

This is a simple question I came across in reviewing. I am wondering if I got the correct answer.

The question is simple. You have $n$ balls and $m$ bins. Each ball has an equal probability of landing in any bin. I want to know what the probability that exactly $1$ bin is empty.

My answer seems simple enough, but I don't think it's sufficient. It is $(\frac{m-1}{m})^n$ since for each ball, it can go in any of the other bins. I think, however, that this is just the probability that some arbitrary bin $A$ is empty, not exactly one bin. What else should I consider?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ If you want to see lots of variations to this type of problem, check out the Twelvefold Way. A good place to see this is in Stanley's book and you can get the second edition free for now. $\endgroup$ – Graphth Apr 12 '11 at 2:41
  • 12
    $\begingroup$ @Douglas: I agree with your last comment, up to and including with this question, but I disagree with the rest of it. Yes your solution is correct, yes the accepted one is flagrantly wrong, yes you did everything you could to explain things, patiently, going back to the basics, giving elementary examples, as one should do in such cases. And all this did not work with the OP and a few others. So what? Is this the first time you see such things happening here? Is this enough to declare the site worthless? I do not think so. So, please forget the noise and keep up the good job. $\endgroup$ – Did Apr 12 '11 at 8:28
  • 5
    $\begingroup$ I just voted up Douglas's answer and voted down the other one. Nothing personal here, no implication of any sort, this is simply to signal that one solution is wrong and the other one is correct. $\endgroup$ – Did Apr 12 '11 at 8:31
  • 4
    $\begingroup$ @Douglas: It occasionally occurs that erroneous answers are temporarily upvoted higher than correct ones. However this is usually rectified very quickly once the error has been pointed out. If all else fails it can be discussed on meta. It seems you've had the bad luck of encountering a few anomalous threads in your initial experiences here. Don't let them spoil your impression of the entire site. If you browse the prior questions you'll see that such situations are by far the exception rather than the rule. $\endgroup$ – Bill Dubuque Apr 12 '11 at 16:50
  • 3
    $\begingroup$ I've updated the accept to the correct solution. Thanks to everybody for the explanations. $\endgroup$ – user9470 Apr 12 '11 at 18:06
32
$\begingroup$

Let's count configurations, and then divide by $m^n$.

There are $m$ choices for the empty bin. Then the other bins are occupied. We can count the ways to place $n$ balls in $m-1$ bins so that no bin is empty by inclusion-exclusion: It is

$$\sum_{k ~\text {bins known to be empty}} (-1)^k {m-1 \choose k} (m-1-k)^n.$$

Another way to get this is to label the parts of a set partition of size $n$ with $m-1$ parts. The number of set partitions with a given number of parts is a Stirling number of the second kind, and we want $(m-1)! S(n,m-1)$.

Multiply this by $m$ and then divide by $m^n$ to get the probability exactly $1$ bin is empty.

We can use the same techniques to compute the probability exactly $e$ bins are empty for other values of $e$. For example, suppose there are $4$ bins and $6$ balls. Then there are $1560$ ways for there to be $0$ empty bins, $2160$ ways for there to be exactly $1$ empty bin, $372$ ways for there to be exactly $2$ empty bins, and $4$ ways for there to be exactly $3$ empty bins. The total is $4096 = 4^6$. Dividing by this gives a probability of $\frac{135}{256} = 0.52734375$ that exactly $1$ bin is empty.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ My experience is if you get an explanation you can improve it, but an explanation is unlikely. +1 from me. $\endgroup$ – Ross Millikan Apr 12 '11 at 4:24
  • 2
    $\begingroup$ For more information on the inclusion-exclusion method, please follow the link to Wikipedia. That explains why I have a sum indexed like that. You can check it against the explicit example I did for $4$ bins and $6$ balls. If that's not enough exposition for you, ask someone else. $\endgroup$ – Douglas Zare Apr 12 '11 at 6:57
  • 11
    $\begingroup$ @Douglas: Please don't leave the site over this one. One gets stray downvotes occasionally. I have upvoted your answer and asked OP to move the accept over here. $\endgroup$ – Ross Millikan Apr 12 '11 at 13:48
  • 3
    $\begingroup$ @Douglas: If anyone would have flagged the comment when he made it, the moderators would have known about it and taken appropriate action. But no one did flag it, so the moderators didn't know about it, so I don't see why you're upset with me. I understand your desire to respond to whuber's comment (I have now read it), but a more appropriate course of action would have to flag it asking for a moderator to delete it. I think there's no value in keeping these comments that only record a sore argument that was resolved a year ago; I am going to delete them, unless you have a good reason not to. $\endgroup$ – Zev Chonoles Apr 15 '13 at 3:20
  • 4
    $\begingroup$ @Douglas: Within minutes of seeing your response, whuber deleted his comment and flagged yours. $\endgroup$ – Zev Chonoles Apr 21 '13 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy