Feedback on "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


Feedback from Brendan McKay

Hi Doron,

About your balls in bins problem, I don't have time to figure out the details, but here is how to do it.

Let Z be the n-dimensional random variable for one round. (I.e. it has binom(n,r) possible values with equal probability.)

Then the random variable X for T rounds is the sum of T independent copies of Z, so it satisfies the central limit theorem. That is, asymptotically X has a normal distribution N with mean and covariance matrix T times those of Z.

Note that it is a singular distribution (one zero eigenvalue) coming from the sum of the entries being fixed at rT.

The maximum component of X will asymptotically have the same mean as the maximum component of N.

Alas the maximum component of N is not a trivial problem and there may not be closed formulas. The density of the maximum is given by Corollary 5 of

this

I don't know if a simple expression for the mean results from that density. A numerical evaluation will show if this is on the right track.

If you want more precision than a normal distribution, the Edgeworth Theorem for multivariable lattice distributions gives any desired accuracy but it isn't easy to work with.

Cheers, Brendan.


Posted: May 21, 2019



Back to article