Coupon collector's problem revisited (brute force calculation)

Solution 1:

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.

Solution 2:

This is merely an answer outline than an answer, for now.
Let $\mathbf{p}_n=(p_1,p_2,p_3,p_4,p_5)^T$ and $p_i$ be the probability of having $i$ distinct coupons after opening $n$ boxes. $\mathbf{p}_1=(1,0,0,0,0)^T$ and $\mathbf{p}_n=A\mathbf{p}_{n-1}$ where $$ A=\begin{pmatrix} 0.2 && 0.8 && 0 && 0 && 0\\ 0 && 0.4 && 0.6 && 0 && 0\\ 0 && 0 && 0.6 && 0.4 && 0\\ 0 && 0 && 0 && 0.8 && 0.2\\ 0 && 0 && 0 && 0 && 1 \end{pmatrix}^T$$ The step I'm not sure about: the probability of getting the full of $5$ distinct coupons after opening exactly $n$ boxes is $0.2(0,0,0,1,0)\mathbf{p}_{n-1}$ as one have to have exactly $4$ distinct coupons after opening $n-1$ boxes and the $5$th will be different with probability $0.2$.
And the desired estimate is $0.2\sum\limits_{n=2}^\infty n(0,0,0,1,0)A^{n-2}\mathbf{p}_1$
Now I want to mention that $(A-I)$ based approach doesn't work as $|A-I|=0$ so we can't take $(A-I)^{-1}.$
So we have at least $3$ ways to finish the rest:
1. Get the diagonalization of $A$ then compute $A^n$ and explicitly then perform the summation.
2. When not considering $p_5$ the $A$ will be $4\times 4$ with eigenvalues $0.2,\,0.4,\,0.6,\,0.8$ so we can $(A-I)^{-1}$ now.
3. Let $A=D+B$ where $D$ is a diagonal matrix and $B^k=0$ for some $k$ and then use $(D+B)^n=\sum\limits_{k=0}^n {n\choose k}D^kB^{n-k}$ as it will have a constant anoumt of terms.
I'd like to perform options $1.$ and $3.$
1. By performing explicit computations we get that $p_4(n)=-\frac{4}{5^n} + \frac{3\cdot 2^{2 + n}}{5^n} - \frac{4\cdot 3^{1 + n}}{5^n} + \frac{4^{1 + n}}{5^n}$ and the summation gives the right answer of $\frac{137}{12}$.