2

I encountered this problem. There are $M$ boxes and $N$ balls. Balls are thrown to the boxes randomly with probability of $\frac1M$. The boxes are numbered $1, 2, 3, ..., M$. what is the probability of last $i$ slots are empty, $i = 1, 2, 3, ...,M-1$?

I appreciate any insight on the problem.

Abraham Zhang
  • 894
robithoh
  • 91

1 Answers1

1

There are $M^N$ functions from the set of balls to the set of boxes, all equally likely. The number of functions that miss $i$ specific boxes is $(M-i)^N$.

Equivalently, the probability that the first ball misses $i$ specified boxes is $\frac{M-i}{M}$. By independence, the probability they all do is $\left(\frac{M-i}{M}\right)^N$.

André Nicolas
  • 507,029
  • Thank you Andre Nicolas. I have further question, when the probability is not uniform ( $1/M$). i.e. probability of throwing the balls to box 1,2,..., $M$ are $p_1$ , $p_2$,..., $p_M$, respectively. – robithoh Mar 17 '14 at 07:59
  • In that case, the probability the last $i$ are empty is $(p_1+p_2+\cdots+p_{M-i})^N$. – André Nicolas Mar 17 '14 at 13:04