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.

# Maple package

• BINnr.txt, a Maple package to analyze the maximal number of balls in a bin upon throwing r balls into n bins T times

# Sample Input and Output for BINnr.txt

• If you want to see the recurrence, in T, for the sequence of averages of the maximal number of balls in a bin when 1 ball is thrown into 2 bins T times, and the implied estimate for the constant C such that
A(T)=T/2+C*sqrt(T), that happens to be
C=0.3989

the input file generates the output file.

• If you want to see the recurrence, in T, for the sequence of averages of the maximal number of balls in a bin when 1 ball is thrown into 3 bins T times, and the implied estimate for the constant C such that
A(T)=T/3+C*sqrt(T), that happens to be
C=0.489

the input file generates the output file.

• If you want to see the recurrence, in T, for the sequence of averages of the maximal number of balls in a bin when 1 ball is thrown into 4 bins T times, and the implied estimate for the constant C such that
A(T)=T/4+C*sqrt(T), that happens to be
C=0.516

the input file generates the output file.

• If you want to see the recurrence, in T, for the sequence of averages of the maximal number of balls in a bin when 2 balls are thrown into 4 bins T times, and the implied estimate for the constant C such that
A(T)=T/2+C*sqrt(T), that happens to be
C=0.59430

the input file generates the output file.

Articles of Doron Zeilberger