Guessing the length of a playlist on "shuffle random?"?

Question

The other night I was hanging out with some friends and someone put on a playlist on shuffle random, where the songs are drawn uniformly at random from a fixed playlist. The person who put the playlist together forgot how many songs were in it, so the topic came up of how to estimate the size of the playlist purely based on what we hearing. We came up with a few high-level ideas for how to do this. For example, using ideas from the Birthday Paradox, we thought we could listen until we heard a song repeated for the first time, then use that to make an educated guess about how many songs were on the playlist in total. We also thought that we could listen for a long time and build up a frequency histogram of the number of times each song was played, then use the fact that it should look somewhat normally distributed to get the mean and variance and from there estimate the total number of songs on the list. None of us are statisticians or have a lot of training in machine learning, but I suspect that this is probably a well-studied problem and that there are some really nice techniques we can use to estimate the playlist size. Are there a good family of techniques for estimating the playlist size? From a practical perspective, would any of these techniques be something that would be relatively easy to work out without a computer or calculator? Thanks!

Answer 1

That's a good example and just like any other problem, this could be solved in a lot of ways.

One method I could think of is this:

Let N= total number of songs in the playlist

P = number of songs that you will play (i.e. how many songs in total do you want to listen to)

K= number of songs you will keep track (you have to set this number)

1. Listen to the playlist and play K songs (you have to preselect this number K).Take note of the title of all of the K songs.
2. Now play the playlist again until P songs were played.
3. Count the number, call it n, among the P songs played that were played in Step 1.
4. Then an estimate of N = (P*K)/n

The estimate is based on an assumption that the proportion

P/N = n/k

i.e. proportion of song played = proportion of songs that were played again among those that were played before

And just like any parameter in statistics, there is a wide variety of possibly estimators for N.Could even do a Monte Carlo study on this approach.