Repository logo
 

Tight Bounds for Repeated Balls-Into-Bins

Published version
Peer-reviewed

Repository DOI


Loading...
Thumbnail Image

Type

Conference Object

Change log

Authors

Sauerwald, T 

Abstract

We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta (2019). This process starts with m balls arbitrarily distributed across n bins. At each round t = 1, 2, ... , one ball is selected from each non-empty bin, and then placed it into a bin chosen independently and uniformly at random.

We prove the following results: • For any n ≤ m ≤ poly(n), we prove a lower bound of Ω(m/n · log n) on the maximum load. For the special case m = n, this matches the upper bound of O(log n), as shown in [BCNPP19]. It also provides a positive answer to the conjecture in [BCNPP19] that for m = n the maximum load is ω(log n / log log n) at least once in a polynomially large time interval. For m in [ω(n), n log n], our new lower bound disproves the conjecture in [BCNPP19] that the maximum load remains O(log n). • For any n ≤ m ≤ poly(n), we prove an upper bound of O(m/n · log n) on the maximum load for all steps of a polynomially large time interval. This matches our lower bound up to multiplicative constants. • For any m ≥ n, our analysis also implies an O(m²/n) waiting time to reach a configuration with a O(m/n · log m) maximum load, even for worst-case initial distributions. • For any m ≥ n, we show that every ball visits every bin in O(m log m) rounds. For m = n, this improves the previous upper bound of O(n log² n) in [BCNPP19]. We also prove that the upper bound is tight up to multiplicative constants for any n ≤ m ≤ poly(n).

Description

Keywords

Journal Title

Leibniz International Proceedings in Informatics, LIPIcs

Conference Name

40th International Symposium on Theoretical Aspects of Computer Science (STACS'23)

Journal ISSN

1868-8969

Volume Title

254

Publisher