Distribute (completely at random) $m$ balls into $n$ bins.

Now if I distribute one additional ball into the $n$ bins, what's the probability that this ball will land in an empty bin?


Hint. First determine how many empty bins there are after distributing the first $m$ balls; call this number $B$. The answer is then $E(B)/n$. Note that we need only calculate $E(B)$; the precise distribution of $B$ is not required.

The probability that a particular bin is empty is simply $\bigl(\tfrac{n-1}{n}\bigr)^m$, since all $m$ balls must not fall into it. We now want the expected number, so we simply sum this over all the bins to get $n \bigl(\tfrac{n-1}{n}\bigr)^m$.

Hence the final answer is $\bigl(\tfrac{n-1}{n}\bigr)^m$.

Can you justify why the two probabilities I've calculated are the same? In particular, if you can then you will be able to come up with a shorter, more direct proof. I leave this as an exercise that I strongly encourage you to do, as it will enhance your understanding of this, and related, problems.

As a follow up, consider this. The extra ball that you place chooses a bin uniformly at random, and independently of the way the balls are distributed. So all that matters is whether or not that one bin is empty. It doesn't matter how many are empty. So ask which bin was selected, then determine the probability of that bin being empty. For any fixed bin, as above, the probability is simply $\bigl(\tfrac{n-1}{n}\bigr)^m$. Since the bin is chosen independently of the distribution, this is the final answer.

Alternatively, we can 'do a wlog'. Since the bin is chosen independently and the balls are distributed 'uniformly', all the bins have the same distribution. Thus, without loss of generality (wlog), we may assume that the extra ball is placed in the first bin. Then we just need to determine the probability that this bin is empty, which, again, is just $\bigl(\tfrac{n-1}{n}\bigr)^m$. You may well find this easier to understand since now a bin is being chosen deterministically, as opposed to randomly. The two methods are, of course, basically the same.

  • $\begingroup$ My approach was: the probability of a particular bin being empty after distributing $m$ balls is $(n-1/n)^m$. Then, the probability of the additional ball being put into this particular bin is $(n-1/n)^m∗1/n$. Because there are $n$ choices to choose this particular bin, the probability of a ball being put into an empty bin is $(n-1/n)^m ∗ 1/n∗n=(n-1/n)^m$. $\endgroup$ – Anna Vopureta Oct 25 '17 at 15:13
  • $\begingroup$ Is that the direct proof you are referring to? $\endgroup$ – Anna Vopureta Oct 25 '17 at 15:44
  • $\begingroup$ Not quite. What you've written is basically the same as what I said. Note that you've written $n-1/n$ above whereas it should be $(n-1)/n$: there are $n-1$ bins that are not the bin in question. \\ I've updated my answer to add what I was meaning. $\endgroup$ – Sam T Oct 26 '17 at 9:59

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.