Balls and Bins -- Simple Concentration Bounds

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 \|p\|_k / k\). This gives concentration inequalities for the maximum load...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-05
Main Authors: Schulte-Geers, Ernst, Waggoner, Bo
Format: Article
Language:English
Subjects:
Bins
Throwing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \|p\|_k / k\). This gives concentration inequalities for the maximum load as well as for the waiting time until a \(k\)-loaded bin.
ISSN:2331-8422