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.

Question 1: What is P{X $=$ 0}?

If there is no empty bin, every ball must land into different bin. In this case, the first ball has n choices, the second ball has n-1 choices, and in general the i-th ball has n - i +1 choices. Therefore, there are $n\cdot (n-1)\cdot (n-2)\cdots (2)(1)=n!$ outcomes. The probability is ${\frac {n!}{n^{n}}}$.

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