Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics, and probability / Probability / 7 / b / v / Solution

By linearity of expectation, $\mathbb{E}{N}_n=n{p}_n$. The variance of a sum and the negative covariance just proved giveApply Chebyshev's inequality to the empty-box indicators in uniform allocation: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}$.