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?

  • 3
    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](http://www-math.mit.edu/~rstan/ec/ec1/) free for now.2011-04-12
  • 0
    Consider 3 balls and 2 bins as a toy case.2011-04-12
  • 0
    This is close to case $3$ in Stanley's _Enumerative Combinatorics Volume 1_ page $81$.2011-04-12
  • 2
    There is a flagrantly incorrect answer that was voted up and accepted, while people voted down my correct and informative answer. I'm done with this question and maybe this site. This is a waste of my time.2011-04-12
  • 12
    @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.2011-04-12
  • 5
    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.2011-04-12
  • 2
    @domo_glue: please unaccept my answer, as Douglas Zare has shown it wrong-even accept his. I will either fix or delete it then. Thanks.2011-04-12
  • 4
    @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.2011-04-12
  • 3
    I've updated the accept to the correct solution. Thanks to everybody for the explanations.2011-04-12

1 Answers 1

32

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.

  • 0
    Please explain your down vote.2011-04-12
  • 2
    My experience is if you get an explanation you can improve it, but an explanation is unlikely. +1 from me.2011-04-12
  • 0
    Douglas: Thanks for adding your answer to the mix. But I don't follow: you have your summation indexed by "$k$ bins known to be empty". How do you evaluate a summation based on what "is known"? I would suggest you improve your answer by clarifying this. Also, your answer doesn't have an answer explicitly stated anywhere (that I can find). I think it would be an improvement to highlight the answer for "exactly one bin empty" rather than leaving it to the reader to "multiply by $m$ and divide by $m^n$" and simplify. (Unless you were intending to give only a hint?!) Finally...2011-04-12
  • 1
    I said "Let's count the configurations, then divide by $m^n$." Then I counted the configurations as $m$ times that sum. How can you say that's just a hint? I'm sorry you don't think that sum is as clear as an incorrect answer, but not everything is that simple.2011-04-12
  • 2
    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.2011-04-12
  • 11
    @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.2011-04-12
  • 0
    @Douglas: I also don't understand what you mean by "$k$ bins known to be empty". In a summation, I'd like to see what values of $k$ should be taken into account, either by writing down the set of all the values or by specifying a condition on $k$ such as "$k$ is a divisor of $m$". I'd like to know what the set/condition in your summation is. Thanks in advance!2011-04-12
  • 0
    @whuber: I spent hours showing that the accepted answer was incorrect. You made a stupid comment on my correct answer, objecting to my use of a prior on a problem tagged Bayesian, where everyone else uses priors, and where optimization with no prior does not make sense. You had no objection to the incorrect, accepted answer which used the same prior. You refused to apologize or communicate with me other than questionable uses of your moderator powers. This is unacceptable to me, so I will no longer contribute to CV. I do not understand your rudeness or disrespectful attitude.2013-04-12
  • 2
    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.2013-04-12
  • 0
    @Douglas: It seems like this issue was resolved successfully - your answer is now the accepted one, and others have agreed that it is correct. While I understand you still feel upset about the experience you had with this thread, continuing to post comments about it seems futile - in fact, I'm inclined to clean up all of the comments here that are not of a mathematical nature, now that everything is settled. What do you think?2013-04-13
  • 0
    @Zev Chonoles: I think you missed whuber's snarky comment. I'm glad he had the decency to delete it after I responded; too bad it was up for weeks before I noticed, and that he doesn't have the decency to apologize. I reserve the right to defend myself from additional attacks. Would that you were so eager to delete his comment when he made it.2013-04-15
  • 3
    @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.2013-04-15
  • 0
    @Zev Chonoles: I'm not upset with you, but it's odd that you responded within minutes to my response to whuber, while his nasty comment was left for weeks.2013-04-20
  • 4
    @Douglas: Within minutes of seeing your response, whuber deleted his comment and flagged yours.2013-04-21