Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I think this has something to do with the theory of martingales. The famous monkey abracadabra problem is similar to this. mathproblems123.wordpress.com/2010/09/16/… –  Beni Bogosel Mar 27 '11 at 12:00
add comment

3 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
Thanks Alekk for your answer. The problem was born from a computer science issue (about which I ignore the details) and hence in a finite setting, however the limit case is interesting per se. Do you think it is possible to answer also question 2 in the Poisson approximation? –  Ale Zok Mar 27 '11 at 15:10
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.