0

Suppose I have a system that randomly, with uniform distribution, assigns $N$ balls to $M$ identical boxes, where $N \gg M.$ Suppose further that the boxes have some limit as to the number of balls they may each hold. I want to determine the size of boxes I should provide as a practical limit given the number of trials T that I intend to perform. (A trial is an assignment of balls to boxes.)

Obviously, if M is 1, the single box must be able to hold all N balls, and for M > 1, in the worst case, some box must be able to hold all N balls. Yet, in simulations of billions of trials, for M > 1, this worst case doesn't come close to happening. So, how can I determine, for a given number of trials, a practical upper limit on the size of the boxes, such that the likelihood I would need larger boxes is vanishingly small? (I must be able to perform hundreds of billions or even trillions of trials.)

I suspect there is a closed-form solution, but I have been unable to divine it.

Michael Hardy
  • 1
Stephen Morgan
  • 39
  • As Brian has said, it is a multinomial distribution. If you think about the case where $M=2$ you just have a binomial distribution, and will be able to work out that the probability of all balls being in a single box is very small. Multinomials are a little harder to work out but are still well known – Henry Lee Aug 07 '21 at 16:09

1 Answers1

2

Your distribution is a "uniform multinomial distribution".

Check out this question: https://mathoverflow.net/questions/104948/distribution-of-maximum-of-a-uniform-multinomial-distribution

This is also very closely related (minimum box value instead of max): The minimum value of a uniform multinomial distribution

Brian Lai
  • 770