# Ball and bins & Coupon collector problem

If you know a coupon collector problem, you will know what I am talking about. But if you are not familiar with I will try to explain what is the coupon collector problem. I have $n$ bins. I throw balls consecutively into these bins. Each bin is choosen independently and with the same probability. Let's suppose that in one moment, I have $k$ non-empty bins. Let's $T_{n,k}$ be the random variable, which describes how many throws I need to do to have now exactly $k+1$ non-empty bins. $$P(T_{n,k}=m) = (1-\frac{n-k}{n})^{k-1}\frac{n-k}{n}$$ from Geometric distribution.

I want now to evaluate what is the probability that after throwing $m$ balls I have at least $k+1$ non-empty bins. I know that I have to count the probabilities that after throwing $m$ balls I have: $k+1$,$k+2$,$k+3$,...$n$ non-empty bins. But I have problem to count the probabilities for $k+2$, $k+3$,..

I was trying to use binomial distribution. For I have $k$ non-empty bins and I throw $m$ balls. I want to count the probability that now I have $k+2$ non-empty, so at least two balls have to fall into one of $(n-k)$ bins, so I evaluated this as: $${m \choose 2}\left(\frac{n-k}{n}\right)^2\left(1-\frac{n-k}{k}\right)^{m-2}$$ And for $k+3$,$k+4$,...,$n$ it goes the same. Then I only have to sum all this probabilities? Is this correct? Or maybe it is to simple and I didn't noticed something very important?

• That seems right to me. – Ragnar Jan 5 '14 at 0:37

If you know how to compute the probability of having $k+1$ non-empty bins, then you'll need to sum over the probabilities of having $n$ empty bins, $n-1$ empty bins, $\ldots$, $k+1$ empty bins. You can do this with the binomial cumulative distribution formula.

Your expression for $P(T_{n,k}=m)$ is clearly wrong; it doesn't depend on $m$. The exponent should be $m-1$ instead of $k-1$.

The probability of having at least $k+1$ non-empty bins after $m$ throws is the complement of the probability of still having the same $k$ non-empty bins, which is $\left(\frac kn\right)^m$.