Papers › Tight Bounds for Repeated Balls-into-Bins
Tight Bounds for Repeated Balls-into-Bins
Dimitrios Los, Thomas Sauerwald
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 ·logn) on the maximum load. For the special case m=n, this matches the upper bound of O(logn), as shown in [BCNPP19]. It also provides a positive answer to the conjecture in [BCNPP19] that for m=n the maximum load is ω(logn/ loglogn) at least once in a polynomially large time interval. For m∈[ω(n),nlogn], our new lower bound disproves the conjecture in [BCNPP19] that the maximum load remains O(logn). ∙ For any n≤m≤poly(n), we prove an upper bound of O(m/n·logn) 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·logm) maximum load, even for worst-case initial distributions. ∙ For any m ≥n, we show that every ball visits every bin in O(mlogm) 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).
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections