Balls and Bins -- Simple Concentration Bounds

2022/05/28 by Ernst Schulte-Geers, Schulte-Geers, Ernst, Bo Waggoner +1
Computer Science · Engineering · #Algorithms and Data Compression #FOS: Mathematics #Mineral Processing and Grinding #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2205.14494

openalex publication_date 2022/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ρ_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.

Related

• Expected number of uniformly distributed balls in a most loaded bin using placement with simple linear functions
• The power of thinning in balanced allocation
• The Probability to Hit Every Bin with a Linear Number of Balls
• Balls and Bins and the Infinite Process with Random Deletions
• Load Balancing with Dynamic Set of Balls and Bins