Average number of bins occupied when throwing $n$ balls into $N$ bins

Question

There are $n$ balls and $N$ bins.

At each time, a ball is thrown in one bin of $N$ bins at random. This repeats n times. So that in total $n$ balls are thrown into bins.

The question is, on average, how many bins are occupied (with at least one ball in it) in the end.

Thanks.

Answer 1

Define indicator random variables $X_i$ by $X_i=1$ if Bin $i$ ends up occupied, and $X_i=0$ if it does not. Let $Y$ be the number of occupied bins. Then $$Y=X_1+X_2+\cdots+X_N.$$ We want to find $E(Y)$.

The probability Bin $i$ is not occupied is $\left(1-\frac{1}{N}\right)^n$. So the probability it is occupied is $1- \left(1-\frac{1}{N}\right)^n$. Thus the mean of each $X_i$ is $1- \left(1-\frac{1}{N}\right)^n$.

By the linearity of expectation, the mean number of occupied bins is $N\left(1- \left(1-\frac{1}{N}\right)^n\right)$.