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

The Linearity of Expectation

One of the reason why expectations are rather easy to work with is that they have a certain linear property stated as follows.

Linearity of Expectation.

For random variables X and Y, we have that

$\mathrm {E} [X+Y]=\mathrm {E} [X]+\mathrm {E} [Y].$

This is also true for more than one random variable. Let $X_{1},X_{2},\ldots ,X_{k}$ be random variables. Thus,

$\mathrm {E} \left[\sum _{i=1}^{k}X_{i}\right]=\sum _{i=1}^{k}\mathrm {E} [X_{i}].$

This property is always true even when they are dependent.

This also leads to various nice properties of expectation. A very useful fact is this: for constants a and c, $E[aX+c]=a\cdot E[X]+c$.

Using the linearity of expectation

In order to deal with complicated random variables such as X above, we can break it down into "simpler" random variables.

For bin i, we define a random variable X_i to be 1 if bin i is empty and 0 otherwise. Note that with this definition, we have that

$X=\sum _{i=1}^{n}X_{i}$.

(You should think for a few minutes so that you understand this.)

This implies that $\mathrm {E} [X]=\mathrm {E} \left[\sum _{i=1}^{n}X_{i}\right]$, because the expectations of two equal things must be equal.

Note that we use each random variable X_i to indicate if each bin is empty. This type of random variables is generally referred to as indicator random variables.

Since we know that X is the sum of other random variables, the linearity of expectation tells us that

$\mathrm {E} \left[\sum _{i=1}^{n}X_{i}\right]=\sum _{i=1}^{n}\mathrm {E} [X_{i}]$.

Therefore, if we can find $\mathrm {E} [X_{i}]$ then we are done. So let's consider indicator random variable X_i. From the definition, we have that

$\mathrm {E} [X_{i}]=0\cdot P\{X_{i}=0\}+1\cdot P\{X_{i}=1\}$,

which clearly is $P\{X_{i}=1\}.$

So, when does X_i is 1? This, by the definition of X_i, is equivalent to the event that bin i is empty that we have already calculated in Question 2. Thus,

$\mathrm {E} [X_{i}]=\left(1-{\frac {1}{n}}\right)^{n}$.

This implies that

${\begin{array}{rcl}\mathrm {E} [X]&=&\mathrm {E} \left[\sum _{i=1}^{n}X_{i}\right]\\&=&\sum _{i=1}^{n}\mathrm {E} [X_{i}]\\&=&\sum _{i=1}^{n}\left(1-{\frac {1}{n}}\right)^{n}\\&=&n\cdot \left(1-{\frac {1}{n}}\right)^{n}.\end{array}}$

Again, the first step is true because $X=\sum _{i=1}^{n}X_{i}$ and the second step is true because of the linearity of expectation.

Note that as n gets close to infinity, $\left(1-1/n\right)^{n}$ is close to $1/e$. Thus, $\mathrm {E} [X]\approx n/e$, or there are about 36.7% empty bins.

Remark: For an indicator random variable A, $\mathrm {E} [A]=P\{A=1\}$.

Fullest bins

In this section, we will try to give a guarantee on the number of balls in the fullest bin.