= Concentration of the empty-box fraction
{title2=$K_n/n\longrightarrow e^{-1}\text{ in probability}$}
For $n$ balls in $n$ uniformly and independently chosen boxes, put $p_n=(1-1/n)^n$. The <empty-box indicators in uniform allocation> have negative pairwise <covariance>, so $\operatorname{var}(K_n)\le np_n(1-p_n)\le n/4$. <Chebyshev's inequality> gives
$$
\mathbb P(|K_n/n-p_n|>\epsilon)\le\frac1{4n\epsilon^2}\longrightarrow0.
$$
Since $p_n\to e^{-1}$, this proves the displayed <convergence in probability>. The centring and the negative <covariance> are essential to this short proof; an <expectation> limit alone would not establish concentration.
Back to article page
