Journal of Integer Sequences, Vol. 23 (2020), Article 20.1.7

A Short Note on the Average Maximal Number of Balls in a Bin


Marcus Michelen
University of Illinois at Chicago
Department of Mathematics, Statistics and Computer Science
Chicago, IL 60607-7045
USA

Abstract:

We analyze the asymptotic behavior of the average maximal number of balls in a bin obtained by throwing uniformly at random r balls without replacement into n bins, T times. Writing the expected maximum as

\begin{displaymath}\frac{r}{n}T+ C_{n,r}\sqrt{T} + o(\sqrt{T}),\end{displaymath}

a recent preprint of Behrouzi-Far and Zeilberger asks for an explicit expression for Cn,r in terms of n,r and $\pi$. In this short note, we find an expression for Cn,r in terms of n, r and the expected maximum of n independent standard Gaussians. This provides asymptotics for large n as well as closed forms for small n--e.g., $C_{4,2} = \frac{3}{2
\pi^{3/2}} \arccos(-1/3)$--and shows that computing a closed form for Cn,r is precisely as hard as the difficult question of finding the expected maximum of n independent standard Gaussians.


Full version:  pdf,    dvi,    ps,    latex    


Received August 19 2019; revised versions received October 17 2019; October 23 2019. Published in Journal of Integer Sequences, December 30 2019.


Return to Journal of Integer Sequences home page