5
$\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?

$\endgroup$
9
  • 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$
    – GeoffDS
    Apr 12, 2011 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, 2011 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, 2011 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, 2011 at 16:50
  • 3
    $\begingroup$ I've updated the accept to the correct solution. Thanks to everybody for the explanations. $\endgroup$
    – user9470
    Apr 12, 2011 at 18:06

1 Answer 1

Reset to default
34
$\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.

$\endgroup$
14
  • 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, 2011 at 4:24
  • 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, 2011 at 13:48
  • 3
    $\begingroup$ Here you might have missed the context of the comments on the deleted answer, where multiple people were repeating that I was wrong when I pointed out simple cases which my answer handles correctly, but which were not enumerated correctly by the then-accepted answer. The pattern is that I don't like it when I post something correct, and then multiple people say something clearly incorrect is better. I'm not always right, but I value correctness, and having a club of people praising each other's incorrect answers and voting down my correct answers is intolerable to me. $\endgroup$
    – Douglas Zare
    Apr 12, 2013 at 23:33
  • 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, 2013 at 3:20
  • 4
    $\begingroup$ @Douglas: Within minutes of seeing your response, whuber deleted his comment and flagged yours. $\endgroup$
    – Zev Chonoles
    Apr 21, 2013 at 2:30

Your Answer

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