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

by Amir Behrouzi-Far and Doron Zeilberger

.pdf   .ps   .tex

First Written: May 20, 2019. This version: May 23, 2019.

You play the following game, consisting of T rounds. At each round, you throw r balls into n bins, in such a way that every bin gets at most one ball (for that round).

From the point of view of each individual bin, its probability of getting a ball at any given round is r/n, hence the distribution of its number of balls after T rounds, is the good-old binomial distribution B(T;r/n), about which everything is known.

But suppose that the bins are competitive, and compete for the largest number of balls. Of course it is unlikely that any particular bin will have more than a few standard-deviations above its mean of (r/n)T, hence the random variable

"maximum number of balls in a bin take away its average"

should, asymptotitcally, have an average like a constant, let's call it, Cn,r, times T1/2. It is easy to see (see the paper) that C2,1=(2π)-1/2, but we have no clue about the general expression, in terms, of n and r, and one of us (DZ) is pledging a $50 donation to the OEIS for an explicit expression in terms of n and π for Cn,1, and a further $100 for an explicit expression in terms of n, r, and π for the general Cn,r.

Added May 23, 2019: Marcus Michelen has solved this problem (well, to the extent possible). A donation of $150 to the OEIS, in honor of Marcus Michelen, has been made.

Added May 21, 2019: Read the very interesting comments by Brendan McKay.

Maple package

Sample Input and Output for BINnr.txt

Articles of Doron Zeilberger

Doron Zeilberger's Home Page