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 givesSince , 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!