Balls and Bins -- Simple Concentration Bounds

Abstract

Concentration bounds are given for throwing balls into bins independently according to a distribution $p$. The probability of a $k$-loaded bin after $m$ balls is shown to be controlled on both sides by ${\rho }_{m,k}:=m\Vert p{\Vert }_k/k$. This gives concentration inequalities for the maximum load as well as for the waiting time until a $k$-loaded bin.

13 pages, 3 figures