On the Average Maximal Number of Balls in a Bin Resulting from Throwing r Balls into n Bins T times

2019/05/19 by Amir Behrouzi-Far, Doron Zeilberger, Behrouzi-Far, Amir +1 · 2 citations
Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1905.07827

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

Abstract

We use the holonomic ansatz to estimate the asymptotic behavior, in T, of the average maximal number of balls in a bin that is obtained when one throws uniformly at random (without replacement) r balls into n bins, T times. Our approach works, in principle, for any fixed n and r. We were able to do the cases (n,r) = (2,1),(3,1),(4,1), (4,2), but things get too complicated for larger values of n and r. We are pledging a $150 donation to the OEIS for an explicit expression, (in terms of n, r, and π) for the constant C_n,r such that that average equals (n)/(r) T+C_n,r √(T)+O(1/√(T)). In this version we announce that the problem has been solved (to the extent possible) by Marcus Michelen.

Cited by

• A Short Note on the Average Maximal Number of Balls in a Bin
• Redundancy Scheduling in Systems with Bi-Modal Job Service Time Distribution

Related

• A Short Note on the Average Maximal Number of Balls in a Bin
• The Probability to Hit Every Bin with a Linear Number of Balls
• Expected number of uniformly distributed balls in a most loaded bin using placement with simple linear functions
• Balls and Bins and the Infinite Process with Random Deletions
• Balls and Bins -- Simple Concentration Bounds