Suppose that \(n\) balls are tossed into \(n\) bins, where each toss is independent and the ball is equally likely to end up in any bin. What is the expected number of empty bins? What is the expected number of bins with exactly one ball?

To calculate the expected number of empty bins, let \(X_i\) be the indicator random variable that bin \(i\) is empty after tossing and so \(X\) is the random variable that tells us the total number of empty bins.

\[\begin{split} E[X] &= E \left[ \sum\limits_{i=1}^n X_i \right] \\ &= \sum\limits_{i=1}^n E[X_i] \\ \end{split}\]

But what is \(E[X_i]\)? We are dealing with independent Bernoulli trials where the probability of success (no balls in bin \(i\)) is \(1 - \frac{1}{n}\). There are \(n\) such trials and we need a success for each of them. So the probability that bin \(i\) is empty is

\[{n \choose n}\left( 1 - \frac{1}{n} \right)^n \left( \frac{1}{n}\right)^0 = \left(1 - \frac{1}{n} \right)^n \text{.}\]

And so:

\[\begin{split} E[X] &= \sum\limits_{i = 1}^n \left( 1 - \frac{1}{n} \right)^n \\ &= n \left( 1 - \frac{1}{n} \right)^n\\ \end{split}\]

To calculate the expected number of bins with one ball, let \(Y_i\) be the indicator random variable that bin \(i\) contains exactly one ball. Similarly, \(Y\) is the random variable that tells us the total number of bins with one ball:

\[\begin{split} E[Y] &= E \left[ \sum\limits_{i=1}^n Y_i \right] \\ &= \sum\limits_{i=1}^n E[Y_i] \\ \end{split}\]

We are once again dealing with independent Bernoulli trials, but this time we want one failure and \(n-1\) successes. This probability is

\[{n \choose n-1}\left( 1 - \frac{1}{n} \right)^{n-1} \left( \frac{1}{n}\right)^1 = n \left(1 - \frac{1}{n} \right)^{n-1} \frac{1}{n} = \left(1 - \frac{1}{n} \right)^{n-1} \text{.}\]

And so:

\[\begin{split} E[Y] &= \sum\limits_{i=1}^n \left(1 - \frac{1}{n} \right)^{n-1} \\ &= n \left(1 - \frac{1}{n} \right)^{n-1} \\ \end{split}\]