Mean and variance of the number of empty boxes

Question

You throw n balls independently into n boxes, each ball landing in a uniformly random box. Let X be the number of boxes that end up empty. What are E[X] and \mathrm{Var}(X)?

Accepted Answer

Write X = \sum{j=1}^n Ij, where Ij = 1 iff box j is empty. Mean. Box j is empty iff all n balls miss it, each missing with probability 1 - 1/n: P(Ij = 1) = \left(1 - \frac1night)^n, \qquad E[X] = n\left(1 - \frac1night)^n. As n 	o \infty this tends to n/e, so about 37\% of boxes stay empty. Variance. The indicators are dependent (if one box is empty, its balls landed elsewhere, nudging other boxes fuller). Expand E[X^2] = E[X] + \sum{j 
e k} P(Ij = Ik = 1). Two specific boxes are both empty iff every ball avoids both, each with probability 1 - 2/n: P(Ij = Ik = 1) = \left(1 - \frac2nig…

Mean and variance of the number of empty boxes

Your answer

More Probability questions