[Math] Probability of throwing balls into bins

balls-in-binsprobabilityprobability distributionsprobability theory

You are throwing n balls into m bins randomly.

  1. What is the probability to be empty of the first $k$ bin?

  2. Given $k$ bins are empty. What is the probability to be empty of $(k+1)th$ bin?

  3. Forget the first 2 cases, let throw balls into $m – k$ bins. What is the probability to be empty of the first bin?

Thank you

Best Answer

It is helpful to imagine the balls are distinguishable. That makes no difference to the probability.

There are $m^n$ equally likely ways to distribute the $n$ balls among the $n$ bins. There are $(m-1)^n$ ways to distribute the balls among the last $m-1$ bins. Thus the probability the first bin is empty is $\frac{(m-1)^n}{m^n}$.

Or else when we throw a ball, the probability it misses Bin 1 is $\frac{m-1}{m}$. The probability of missing Bin 1 $n$ times in a row is $\left(\frac{m-1}{m}\right)^n$.

The other problems are solved using similar reasoning.

Related Question