Fun With Spotify and Math
Completely off topic, but as I’ve been listening to my downloaded Spotify collection a lot recently, I was wondering what the average number of songs you have to listen to before you hear the same song twice, assuming random sampling with replacement (which I believe is how the Spotify shuffle works).
So let’s figure it out!
We’ll start by computing the probability that M songs are all different.
First song: We can choose any of the N songs, so there are N possibilities.
Second song: To get a different song, we must avoid the first song, so we have (N-1) favorable outcomes out of N possibilities.
Third song: To get a different song, we must avoid the first two songs, so we have (N-2) favorable outcomes out of N possibilities.
This pattern continues until the Mᵗʰ song.
The probability of selecting M different songs is then:
P(all M songs are different) = N/N × (N-1)/N × (N-2)/N × ... × (N-M+1)/N
This can be simplified to:
P(all M songs are different) = [(N-0)(N-1)(N-2)...(N-M+1)] / [Nᴹ]
This is equivalent to:
P(all M songs are different) = [N!/(N-M)!] / Nᴹ
This formula gives us the probability that when selecting M songs randomly from a playlist of N songs (with replacement), all M selections will be different songs.
So what M gives us P > 0.5?
P(M songs are different) = [N!/(N-M)!] / N^M = 0.5; plug N=100 in;
0.5 = [100!/(100-M)!] / 100^M ==> At M = 12, the probability is approximately 0.5.
So the answer is on average the 12ᵗʰ song will be one of the first 11 and you’ll hear a repeat. That’s a lot smaller than I would have thought!
Note, After The Fact
This problem is the same as the Birthday problem, which I realized after thinking about it a bit more. That link has some super interesting information and results about this problem, which comes up a lot in many contexts. I like things like this where the result is at first counter-intuitive, but when you start thinking about why the result is what it is, the underlying reason becomes clear and improves your intuition about things like this.