1
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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