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?
This is a classic application of indicator random variables and linearity of expectation. We analyze the problem by considering each bin separately.
Expected number of empty bins
Let \(X_i\) be the indicator random variable for the event that bin \(i\) is empty:
\[X_i = \begin{cases} 1 & \text{if bin } i \text{ is empty} \\ 0 & \text{otherwise} \end{cases}\]The probability that bin \(i\) is empty is the probability that all \(n\) balls miss bin \(i\). Since each ball has probability \((n-1)/n\) of missing bin \(i\), and the \(n\) tosses are independent:
\[\begin{align*} \Pr\{\text{bin } i \text{ empty}\} &= \left(\frac{n-1}{n}\right)^n \end{align*}\]By Lemma 5.1, \(\mathrm{E}[X_i] = \Pr\{\text{bin } i \text{ empty}\}\). Let \(X\) be the total number of empty bins:
\[X = \sum_{i=1}^n X_i\]By linearity of expectation:
\[\begin{align*} \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(\frac{n-1}{n}\right)^n \\ &= n \left(\frac{n-1}{n}\right)^n \\ &= n \left(1 - \frac{1}{n}\right)^n \end{align*}\]As \(n \to \infty\), we know that \(\left(1 - 1/n\right)^n \to e^{-1}\). Therefore:
\[\boxed{\mathrm{E}[\text{empty bins}] = n\left(1 - \frac{1}{n}\right)^n \approx \frac{n}{e} \approx 0.368n}\]So roughly 36.8% of bins remain empty when we toss \(n\) balls into \(n\) bins.
Expected number of bins with exactly one ball
Let \(Y_i\) be the indicator random variable for the event that bin \(i\) contains exactly one ball:
\[Y_i = \begin{cases} 1 & \text{if bin } i \text{ has exactly 1 ball} \\ 0 & \text{otherwise} \end{cases}\]For bin \(i\) to contain exactly one ball, we need:
- Exactly one of the \(n\) balls lands in bin \(i\)
- The other \(n-1\) balls land elsewhere
There are \(\binom{n}{1} = n\) ways to choose which ball lands in bin \(i\). That ball has probability \(1/n\) of landing in bin \(i\), and each of the other \(n-1\) balls has probability \((n-1)/n\) of missing bin \(i\):
\[\begin{align*} \Pr\{\text{bin } i \text{ has exactly 1 ball}\} &= \binom{n}{1} \cdot \frac{1}{n} \cdot \left(\frac{n-1}{n}\right)^{n-1} \\ &= n \cdot \frac{1}{n} \cdot \left(\frac{n-1}{n}\right)^{n-1} \\ &= \left(\frac{n-1}{n}\right)^{n-1} \\ &= \left(1 - \frac{1}{n}\right)^{n-1} \end{align*}\]Let \(Y\) be the total number of bins with exactly one ball:
\[Y = \sum_{i=1}^n Y_i\]By linearity of expectation:
\[\begin{align*} \mathrm{E}[Y] &= \sum_{i=1}^n \mathrm{E}[Y_i] \\ &= \sum_{i=1}^n \left(1 - \frac{1}{n}\right)^{n-1} \\ &= n \left(1 - \frac{1}{n}\right)^{n-1} \\ &= n \cdot \frac{\left(1 - \frac{1}{n}\right)^n}{1 - \frac{1}{n}} \\ &= \frac{n}{1 - \frac{1}{n}} \cdot \left(1 - \frac{1}{n}\right)^n \\ &= \frac{n^2}{n-1} \cdot \left(1 - \frac{1}{n}\right)^n \end{align*}\]As \(n \to \infty\):
\[\begin{align*} \mathrm{E}[Y] &\approx \frac{n^2}{n} \cdot e^{-1} \\ &= n \cdot e^{-1} \end{align*}\]Therefore:
\[\boxed{\mathrm{E}[\text{bins with 1 ball}] = n\left(1 - \frac{1}{n}\right)^{n-1} \approx \frac{n}{e} \approx 0.368n}\]Interestingly, the expected number of bins with exactly one ball is the same (asymptotically) as the expected number of empty bins!
Expected number of bins with at least one ball
As a check, the expected number of non-empty bins is:
\[\begin{align*} \mathrm{E}[\text{non-empty}] &= n - \mathrm{E}[\text{empty}] \\ &= n - \frac{n}{e} \\ &= n\left(1 - \frac{1}{e}\right) \\ &\approx 0.632n \end{align*}\]We can verify:
- Empty bins: \(\approx 0.368n\)
- Bins with 1 ball: \(\approx 0.368n\)
- Bins with 2+ balls: \(\approx 0.632n - 0.368n = 0.264n\)