I recently tagged and imported all my mp3 into iTune. I noticed then that there were lots of albums that I had only partially listened to and I decided to use the feature “Party Shuffle” to listen to my library randomly and eventually hear all the songs.
After a couple of weeks, I observed that some songs would reappear in the playlist and were picked twice. Over the weeks the frequency of “re-entry” songs increased with the direct consequence that new music was played less and less. Even though I had already realized that it would not be possible to hear all the songs with approach, I was still surprised by the “re-entry” rate, which I would have intuitively expected to be much lower.
I turned to probability to better understand the situation.
Let’s n be the size of my library. After t songs played randomly, the probability that a given song was played at least once is:
P( song played at least once ) = t / n.
Absolutely not! This probability can be computed with 1 – probability that the song was never played. This gives:
P( song played at least once ) = 1 – (( n-1 )/ n) ^ t
More generally, the probability of a song having been played x times is given by the function
P( x ) = (1/n)^x * ( (n-1) / n )^(t-x) * C ( n, x )
Where C(n,x) is the number of possible permutation. The expanded
P( x ) = (1/n)^x * ( (n-1) / n )^(t-x) * n! / (n-x) ! x!
Note that the probability that the song was never played (x=0) is still (( n-1 )/ n) ^ t.
After t songs, the sum P(0) + P(1) + … + P(t) = 1, which proves that the formula is correct.
The average number of songs played in the library after t songs, can be computed with
Avg. played
= n * P( song played at least once )
= n * ( 1 – ((n-1)/n)^t ) = n – (n-1)^t / n^(t-1)
The “re-entry” rate, or the probability of hearing a new song can be computed with (n- avg. played) / n which is equivalent to the probability that a given song was never played P(x=0).
The graph bellows shows the probability that a song was never played for a library of 500 songs, after 0, 50, 100, etc. songs. It’s interesting to notice that the probability of new songs fall below 50% after about 300 songs.
