From a discussion with some friends, this *apparently easy* problem has come out; I decided to post it here, because I believe that the answer is non-trivial and the maths beneath interesting. Partial solutions, ideas or possible approaches are welcome too!


Suppose that there are $P$ boxes (of infinite capacity) and that every second, I choose a box uniformly at random and I put a bean in it.


1) How many seconds $T$ are at least necessary to have a probability greater than $q \in [0,1]$ of having at least $N$ beans in each box?


2) How many seconds $T$ are at least necessary to have a probability greater than $q \in [0,1]$ of having at least $N$ beans in a fraction at least $f \in [0,1]$ of the total number $P$ of boxes?


I apologize for the "imaginative" formulation of my question, but I hope this choice makes the problem clearer.



Probability estimates for "beans & boxes"
A classical way of tackling such kind of problems is via Poisson approximations.
For example, consider a Poisson point process in $(0,1) \times (0,\infty)$ with unit intensity. The number $N\_k(T)$ of points in $(\frac{k}{P},\frac{k+1}{P}) \times (0,T)$ is distributed as a Poisson random variable with mean $\frac{T}{P}$: this represents an approximation of the number of beans in the $k$-th box at time $T$. Indeed, the advantage of this Poissonization is that the random variables $N\_k(T)$ are now independent - this was not the case in the original problem. The probability that at time $T$ each box contains at least $N$ beans is thus given by $\big(\mathbb{P}[\text{Poiss}(T/P) \geq N] \big)^P$, and you can then do all kind of asymptotic estimates.


I doubt that you will find a very tractable answer to your original question. Are you interested in the limit $N,P \to \infty$ ?


