Probstat/notes/balls and bins

This is part of probstat. These notes are meant to be used in complement to the video lectures. They only contain summary of the materials discussed in the video. Don't use them to avoid watching the clips please.

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.)