= Solution
By <linearity of expectation>, $\mathbb E N_n=np_n$. The <variance of a sum> and the negative <covariance> just proved give
$$
\operatorname{var}(N_n)=np_n(1-p_n)+n(n-1)(q_n-p_n^2)\le np_n(1-p_n)\le\frac n4.
$$
Apply <Chebyshev's inequality> to the <empty-box indicators in uniform allocation>:
$$
\boxed{\mathbb P\!\left(\left|\frac{N_n}{n}-p_n\right|>\epsilon\right)\le\frac{\operatorname{var}(N_n)}{n^2\epsilon^2}\le\frac1{4n\epsilon^2}\longrightarrow0.}
$$
This proves the required <concentration of the empty-box fraction>. Since $p_n\to e^{-1}$, it also yields <convergence in probability> of $N_n/n$ to $e^{-1}$.
Back to article page
