I am assuming a music player drawing songs from a uniform probability distribution, so that for a playlist of $n$ songs, the probability of each song is $\frac1n$ and I want to know how many times I should listen to the playlist in order to hear all the songs. More formally, I want to compute the expected number of played songs until each song has been played once (and divide this by the length of the playlist $n$).
I am using a Markov process approach where each state counts the number of unique songs that have been played, so $q_0$ is the initial state, $q_i$ is the state where exactly $i$ unique songs have been played, and $q_n$ is the last state, where each song has been played at least once. The conditional probabilities are as follows: $$ P(q_i | q_i) = \frac in \\ P(q_{i+1} | q_i) = \frac{n-i}n \textit{ for $i < n$} \\ $$ Notice the special case $P(q_1 | q_0) = 1$ because after the first song we always have one unique song listened to. For all the other states except $q_n$ we have non-zero probabilities for staying in that state or going to the next one. So any listening sequence will see the states in order and stop when $q_n$ is reached. For a sequence $Q = q_0 q_1^{n_1} \ldots q_{n-1}^{n_{n-1}}q_n$, the length of $Q$ (as numbers of songs listened to) is $1 + \sum_{i=1}^{n-1}n_i$ and its probability is: $$ P(Q) = P(q_1|q_0) \cdot \prod_{i=1}^{n-1} P(q_i|q_i)^{n_i-1} \cdot P(q_{i+1}|q_i) = \prod_{i=1}^{n-1}\left(\frac in\right)^{n_i-1}\cdot\frac{n-i}n = \prod_{i=1}^{n-1}\left(\frac in\right)^{n_i} $$ where we have $n_i \geq 1$ and the last equality is obtained by rearranging terms.
With that, the expectation for the length can be written as: $$ E = \sum_{n_i\geq1}\left(1+\sum_{i=1}^{n-1}n_i\right)\cdot\prod_{i=1}^{n-1}\left(\frac in\right)^{n_i} = \prod_{i=1}^{n-1}\frac{\frac in}{1-\frac in} + \sum_{j=1}^{n-1}\frac1{1-\frac jn} \cdot \prod_{i=1}^{n-1}\frac{\frac in}{1-\frac in} = \left( 1 + \sum_{i=1}^{n-1}\frac1{1-\frac in} \right) \cdot \prod_{i=1}^{n-1}\frac{\frac in}{1-\frac in} \\ = \left(1+\sum_{i=1}^{n-1}\frac n{n-i}\right)\cdot\prod_{i=1}^{n-1}\frac i{n-i} = \left(1+\sum_{i=1}^{n-1}\frac ni\right)\cdot\frac{(n-1)!}{(n-1)!} = 1+\sum_{i=1}^{n-1}\frac ni $$ So the number of times I need to listen to my playlist will be $$ \frac En = \frac 1n \cdot \left(1+\sum_{i=1}^{n-1}\frac ni\right) = \sum_{i=1}^n\frac1i $$ Assuming my work is correct, this is a fascinating result, I for one did not expect it when I got started on this problem. Now my question is: how can I obtain the formula for $E$ from the linearity of expectation? From the formula it seems like it should be possible, but it's unclear to me how to formulate the expectations which are summed there.