Coupon collector’s problem revisited (brute force calculation)

algebra-precalculuscombinatoricscoupon-collectorexpected valueprobability

I was trying to solve coupon collector problem for $5$ coupons using brute force calculation, but gave up and say the simple expected value based solution. The question goes like this:

Coupon in cereal box are numbered from $1$ to $5$. A set of each coupon is required for prize. With one coupon per box, how many boxes are required on average for a complete set.

For this I assumed for first $l_1$ tries only $1$ appears and then onwards for $l_2$ only $1, 2$ and so forth till $l_4$ where $1, 2, 3, 4$ appear and after that $5$ appears. So our answer will be

$$\sum_{l_1, l_2, l_3, l_4\ge 1}(l_1+l_2+l_3+l_4+1)\times\frac{1^{l_1} 2^{l_2} 3^{l_3}4^{l_4}}{5^{l_1+l_2+l_3+l_4+1}}$$

Is there a way to salvage this bruteforce approach? Any hints are appreciated

Best Answer

Your sum isn't quite correct, as I mention in the comments, but it's only off by a constant factor (it should be multiplied by $5$), so I'll ignore that in the calculation.

First, generalize it by replacing a factor of $\frac1{5^{l_1 + l_2 + l_3 + l_4}}$ by $x^{l_1 + l_2 + l_3 + l_4}$, where $x = \frac15$. Then we have $$ \sum_{l_1, l_2, l_3, l_4 \ge 1} (l_1 + l_2 + l_3 + l_4 + 1) x^{l_1 + l_2 + l_3 + l_4} \left(\frac{1^{l_1} 2^{l_2} 3^{l_3} 4^{l_4}}{5}\right). $$ This is the derivative with respect to $x$ of the following simpler sum: $$ \sum_{l_1, l_2, l_3, l_4 \ge 1} x^{l_1 + l_2 + l_3 + l_4 + 1} \left(\frac{1^{l_1} 2^{l_2} 3^{l_3} 4^{l_4}}{5}\right). $$ (That's a standard trick for dealing with inconvenient linear factors; you should watch out for it in the future.)

This is now the product of four geometric series: it is $$ \frac{x}{5} \left(\sum_{l_1 \ge 1} x^{l_1}\right) \left(\sum_{l_2 \ge 1} (2x)^{l_2}\right) \left(\sum_{l_3 \ge 1} (3x)^{l_3}\right) \left(\sum_{l_4 \ge 1} (4x)^{l_4}\right) $$ which we simplify to $$ \frac x5 \cdot \frac{x}{1-x} \cdot \frac{2x}{1-2x} \cdot \frac{3x}{1-3x} \cdot \frac{4x}{1-4x}. $$ Now take the derivative of this with respect to $x$: we get $$ \frac x5 \cdot \frac{x}{1-x} \cdot \frac{2x}{1-2x} \cdot \frac{3x}{1-3x} \cdot \frac{4x}{1-4x} \cdot \left(\frac1x + \frac1{x-x^2} + \frac1{x-2x^2} + \frac1{x-3x^2} + \frac1{x - 4x^2}\right). $$ Evaluate at $x = \frac15$ and you get the answer.

Related Question