Coupon Collector Problem with a constant probability of getting a coupon

97 Views Asked by At

My question includes a simple modification to well-known Coupon Collector Problem.

In this version there is a constant probability of getting a coupon at each trial. How this changes the original problem?

Denote by $T_m$ the number of trial required to collect all m coupons. Denote by $p$ the probability of getting a coupon at a trial.

I think the expectation of $T_m$ is simply $$\rm E[T_m] = \frac{m}{p} \sum_{I=1}^m \frac{1}{i}.$$

However, I am not sure about the distribution of $T_m$. I think it may include a Binomial distribution. Can you help about that?

Thanks in advance

1

There are 1 best solutions below

2
On

Look at the accepted answer here to see how to compute the distribution in the standard problem. For the modified problem it should be straightforward to generalize this.

We can imagine that we have $m$ ordinary coupons, each of which occurs with probability $\frac pn$, and one blank coupon, which occurs with probability $1-p$. For $M>=m$ we want the probability $\pi_M$ that in $M$ trials we collect all $m$ non-blank coupons. (If we want the probability that it takes exactly $M$ trials to get all the non-blank-coupons, this is simply $\pi_M-\pi_{M-1}$.)

This is the sum from $k=0$ to $k=M-m$ that we collect exactly $k$ blank coupons, and in the other $M-k$ trails, we collect only non-blank coupons, and get at least one of each. The second part of this is just an ordinary coupon collector's problem.

This will be a messy expression. I don't know if it simplifies at all.