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

h o_{m, k} := m | p |_{k} / k

. This gives concentration inequalities for the maximum load as well as for the waiting time until a

k

-loaded bin.

This page was built for publication: Balls and Bins -- Simple Concentration Bounds