Probstat/notes/balls and bins

This is part of probstat. The materials on this part is from this course at Berkeley.

We consider a balls-and-bins experiment where we throw n balls independently into n bins uniformly at random.

Question 1: How many possible outcomes are there?

Since each ball has n choices and their choices are independent, there are $n^{n}$ outcomes.

Question 2: What is the probability that bin 1 is empty?

In this case, each ball only have n - 1 choices (because they have to avoid bin 1); therefore there are $(n-1)^{n}$ outcomes where bin 1 is empty. Since each outcome is equally likely, the probability that bin 1 is empty is ${\frac {(n-1)^{n}}{n^{n}}}=\left({\frac {n-1}{n}}\right)^{n}=\left(1-{\frac {1}{n}}\right)^{n}$.

Number of empty bins

Let random variable X be the number of empty bins.

{{{1}}}

It will be very hard to compute E[X] directly. (Just computing P{ X = 3 } seems to be exceedingly hard.)