Probability estimates for "beans & boxes"

Question

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.

Answer 1

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$ ?

Answer 2

Your problem falls under the general category of "coupon collector's problems". There is a large literature on such problems, mainly concerned with formulas for the mean and variance of the random variable $T$.

The exact distribution of the time $T$ to have at least one bean ($N=1$) in each box is known in terms of Stirling numbers of the second kind: see Henry's answer here, or below
$$P(\mbox{ every box has at least one bean after }T \mbox{ seconds}) = P^{-T}\ P\ !\ \left\lbrace {T\atop P} \right\rbrace.$$

In general, I think you should take Alekk's advice and use the Poisson approximation.

Answer 3

I'll agree with the other answers that it's easiest to approximate the bins as independent, but since the problem is discrete, it seems more natural to describe the number of beans in a bin by a binomial distribution $B(T,1/P)$. This describes the scenario in which each bin independently can get a bean at each second with probability $1/P$.

Under this approximation then both parts of the question can be answered by computing the distributions of the order statistics of the distribution for $P$ samples. For part 1 it's for the first order statistic (minimum), for part 2 it will be for the $\lceil fP \rceil$-th order statistic.