Concentration of the empty-box fraction

ID: concentration-of-the-empty-box-fraction

For balls in uniformly and independently chosen boxes, put . The empty-box indicators in uniform allocation have negative pairwise covariance, so . Chebyshev's inequality gives
Since , 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.

New to topics? Read the docs here!