2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's simpler to just say that any specific ball has 1/m chance to be in the first bin so the probability all of them aren't in the first bin is (1-1/m)^n=((m-1)/m)^n $\endgroup$ – Tomer Wolberg Feb 5 at 17:42

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.