Average number of collected coupons problem

Question

I have the following problem.

There are two kinds of coupons, $A$ and $B$. Each type has the same probability to be present in a box of cookies. You want to collect a complete set of coupons where there is at least one coupon for each type. What is the average number of boxes of cookies you need to buy?

I parametrize the number of boxes as $n=k_A + k_B$ where $k_{A,B}$ denotes the number of coupons of type $A$ or $B$ that one collects after they bought $n$ boxes. The probability of picking coupon A or B is the same, that is $p=1/2$.

I was thinking to solve this problem in the following way, but since I find a divergence I think my approach is not correct. I want to treat this problem in terms of a multinomial distribution of success variables $k_1$ and $k_2$. The probability mass function would be $$ \rho(k_1,k_2) = \frac{(k_1+k_2)!}{k_1! k_2!}p^{k_1+k_2} $$

from which I can compute the expected value of $k_1 +k_2$ as

$$ \langle k_1 + k_2 \rangle = \frac{\sum_{k_1=0}^{\infty}\sum_{k_2=0}^{\infty} \rho(k_1,k_2) (k_1+k_2)}{\sum_{k_1=0}^{\infty}\sum_{k_2=0}^{\infty} \rho(k_1,k_2)} = \frac{2p}{1-2p} $$

which diverges as I choose $p=1/2$. Of course, this cannot be correct. Where is the problem?

Answer 1

The problem is that the expression that diverges is not an expected value. The probability $\rho(k_1,k_2)$ that you wrote down is the probability to draw $k_1$ and $k_2$ coupons of types $A$ and $B$, respectively, given that $k_1+k_2$ boxes are bought. So to get an expected value, you’d have to sum this over all values of $k_1$ and $k_2$ with that sum, not over all values in general; it’s not surprising that you get a diverging result if you do that. In any case, this expression has nothing to do with the expected value the question asks for, which is the expected value of boxes bought until you have one of each type of coupon. That latter condition doesn’t appear anywhere in your calcuation.

Answer 2

You can assume, without loss of generality, that the first box has coupon A. So the question reduces to how many (more) boxes do you expect to need before finding a coupon B?

Let $E$ denote the expected number of additional boxes needed, after box 1, which is assumed to contain coupon A.

Then

$$E = \frac{1}{2} + \frac{1}{2}(E + 1) = 1 + \frac{1}{2}E \implies E = 2. \tag1 $$

In (1) above, the LHS is explained by considering that $(1/2)$ the time, you will have found coupon B in the second box, and (1/2) the time, your situation will be just as it was, except that you have purchased one extra box.

Therefore, you should expect to need to buy $(E + 1) = 3$ boxes.

Edit
See also the Coupon Collector's Problem. Also, you will find many similarly named mathSE questions posed.

Therefore, this entire question/answer may well be deleted as a duplicate. Until it does, note that the method used in this answer will generalize to other types of Probability Sequence problems besides the Coupon Collector's Problem.