Balls and bins: filling $N$ bins with at least $K$ balls

316 Views Asked by At

Suppose an infinite number of balls are thrown into $N$ bins (uniformly distributed).

What is the expectancy of the number of balls needed in order to fill all bins with at least $K$ balls in each bin.


I found answers to this problem with $K=1$ and even a partial answer to $K=2$ but nothing for the generalized form.

1

There are 1 best solutions below

0
On

I think I found the answer in the following paper:

https://faculty.wharton.upenn.edu/wp-content/uploads/2012/04/Double-dixie-cup-problem.pdf

the expectancy of collecting $m$ balls each bins (having $n$ bins) is:

$$n(\log(n) + (m-1)\log\log n + o(1) )$$

*** this analysis is done for $m$-fixed and $n$-large