I found this little problem interesting. I have not solved it, only thought about how I would go about doing so. We'll see if anyone else thinks it is interesting enough to solve.


Cooped up in your home with nothing better to do, you decide you need to add a soundtrack to your life and create a playlist of the 100 greatest rock and roll songs ever. You order these songs from #1, the all-time best very favorite song, to #100, merely great. You don’t want to play the songs randomly, but also feel that hearing the same order over and over again would get boring. So you come up with some rules to pick which song is played next.

A song to play is chosen randomly with the following criteria:
Songs 1-10 each have a 5% chance of being chosen
Songs 11-20 3% chance
Songs 21-30 1% chance
Songs 31-40 0.75% chance
Songs 41-50 0.25% chance
Songs 51-100 0% chance

When a song is chosen to be played it is put back in the list in one of two slots. 50% of the time it is put into slot #100 and 50% of the time it is put into slot #51. All songs from where the played song is placed move up one slot until the played song’s slot is filled. The next song to be played is then chosen following the rules.

On average, how many songs do you need to listen to before you hear your favorite song for the second time?

Interesting problem. Although maybe not as satisfying, it would be faster for me to code and run the sim a million times than to find an analytic solution.

I can think of two unsexy solutions that basically amount to computerized plug-and-chug. Due to how the probabilities change, I'm not sure a shortcut is possible.

It will take an average of 1/.05=20 plays to hear it the first time.

To hear it twice will take 20 + [E(51) + E(100)]/2

E(100) = E(51) + 49
E(51) = 1 + E(50)
E(50) = 1 + .9975*E(49)
E(49) = 1 + .9975*E(48)
...
E(40) = 1 + .9925*E(39)
...
E(30) = 1 + .99*E(29)
...
E(20) = 1 + .97*E(19)
...
E(10) = 1 + .95*E(9)
...
E(1) = 20

Use E(1) to go up the ladder to E(51).

Another mindless (but powerful and versatile) solution is a Markov chain. You can encode the possible states into a transition matrix, perform a few linear algebra operations and then the answer magically pops out.

A couple of questions (I have no answers).


How do you take into account (or do you need to) slots 49 through 11 don't move up after every play?



How do you take into account (again, do you need to) that once a song gets to slot 10 it has essentially reached the top?

Good point, I didn't need to write the definition I did for E(10). It wasn't wrong, but it's simply 20.

D'oh, I didn't and we do need to. Plus most of my E's were wrong even without that rule.

So then:
E(50) = .0025 + (.5-.0025)*E(50) + .5*E(49)
...
E(40) = .0075 + (.5-.0075)*E(40) + .5*E(39)
...
and so on.

Gahh, FMP:
is what it should be.

Another question I don't have the answer to -



Songs are discrete units; there is no such thing as half a song. If the final answer was something like 47.2568745 songs, you would round up so the answer was 48 songs heard before the favorite plays again. Does this come into play anywhere else in the calculations?



Can you walk through this equation with words? Something doesn't seem quite right to me.

Because it's not. In the post I made after that I fixed it:
There will be at least 1 play no matter what. There will be only 1 play .0025 of the time.
.5-.0025 of the time, a song >10 (but not 50) is chosen, so we're right back where we started.
.5 of the time, a song <11 is chosen and the song bumps up to #49.

I wouldn't, because an EV doesn't have to be a possible outcome. If would round up if I were answering the question, "How many plays do I need for at least an X% chance of this happening?" But for the question of the weighted average, rounding would be wrong. So no, rounding doesn't come up anywhere in the calculation I outlined.

Won't the song bump up to #49 any time a song < 50 is chosen?

E(1 twice) = 1+.95*E(1 twice)+.05*(5*(E51)+.5*(E100))
E(1 twice) = 20+(E(51)+E(100))/2
E(N) = 1+P(x<N)*E(N-1)+P(x>N)*E(N)
E(N) = (1+P(x<N)*E(N-1))/(1-P(x>N))
It should be easy to solve programmatically from here, or by hand if you're really bored.

I think Didace is saying it only bumps up when a song from 1-10 is chosen, otherwise it stays at #50.

That can't be right.



If song 20 is chosen either:
1) slot 51 is chosen, so everything from 21 to 51, inclusive, moves up to repopulate 20 and make room at 51, or
2) slot 100 is chosen, and everything from 21 to 100, inclusive, moves up to repopulate 20 and make room at 100.

Either way, 50 moves up to 49 whenever something above it is played.

This is correct.

Ok then I agree with:

Also note behavior is different for N > 51 because it the song will only move up half the time.

The answer I got is interesting unless I just made a big error. I think it's worth searching for a purely mathematical way to solve this before looking at the spoiler. This is the answer I got programmatically: