Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I managed to figure out how many empty boxes will be left given n amount of throws, just having a hard time figuring out the minimum number of throws necessary so that we have no empty boxes. Would it have to do with the binomial distribution?

share|improve this question
    
Can't have certainty no matter what the number of throws is. So need to specify a proability, like minimum number of throws so that with probability $\gt 0.99$ there are no empty boxes. –  André Nicolas Jun 17 '13 at 23:33
    
@AndréNicolas Or simply the expected number of tosses, rather than a probability threshhold. –  Thomas Andrews Jun 17 '13 at 23:35

2 Answers 2

up vote 2 down vote accepted

The problem is a classical one, usually called the Coupon Collector's Problem. There is a substantial literature. The Wikipedia article linked to gives a reasonably good summary.

If $T$ is the "time" (number of balls) until no box is empty, then the expectation of $T$ is fairly straightforward to get at. It turns out that $$E(T)=nH_n,$$ where $H_n$ is the $n$-th harmonic number, that is, $H(n)=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$. The number $H_n$ grows like $\ln n$. For finer estimates, google harmonic number.

The distribution of $T$ is very complicated. But there are reasonably good tail estimates that let us estimate $\Pr(T\gt t)$ with reasonable accuracy.

share|improve this answer

If $T$ is the "time" (number of balls) until no box is empty, then the distribution of $T$ is easy to describe if you are willing to use Stirling numbers of the second kind. We have for $t\geq n$, $$\mathbb{P}(T\leq t)=n^{-t}\, n!\,{t\brace n}\quad\mbox{and}\quad \mathbb{P}(T = t)=n^{-t}\, n!\,{t-1\brace n-1}.$$

share|improve this answer

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.