Modified coupon collector problem

437 Views Asked by At

I'm considering the original coupon collector problem with a small modification. For the sake of completeness I shall state the original problem again first, where my question is at the end.

say there is a coupon inside every packet of wafers, for the moment let's assume there are only two distinct coupons $C_1$ and $C_2$ that can be collected. How many times do you need to buy the wafers on average to collect both coupons?

The solution to this problem as a classical coupon collector problem is 3. See for example Wikipedia.

Now my question:

How many times on average, should I buy the wafers if I want at least one $C_2$ to be collected before one $C_1$?

2

There are 2 best solutions below

0
On

I am not sure I correctly understand your question. Are you looking for sequences: $C_2C_1,C_2C_2C_1,C_2C_2C_2C_1,...$. If $p$ is the probability of obtaining coupon $C_2$ then probability of a sequence of the sort mentioned which contains $n~C_2$ coupons and $1~C_1$ coupon is $P(n)=p^n(1-p)$. Expected number of wafers to be bought is $\sum_{n=1}^\infty (n+1)P(n)=p(2-p)/(1-p)$ for $0<p<1$. The result makes no sense for $p=0$ because there are no $C_2$ coupons to be had.

0
On

I'm not sure I understand the problem either, but do you mean "how many packets (on average) do I have to buy to get a $C_2$ followed by a $C_1$"?

If so, the answer is $4$. You want the next $C_1$ after the first $C_2$. The expected number of packets up to and including the first $C_2$ is $2$ (expectation of a geometric random variable), and then the expected number of packets after that up to and including the next $C_1$ is also $2$.