You have a playlist with exactly 100 tracks (i.e., songs), numbered 1 to 100. To go to another track, there are two buttons you can press: (1) “Next,” which will take you to the next track in the list or back to song 1 if you are currently on track 100, and (2) “Random,” which will take you to a track chosen uniformly from among the 100 tracks. Pressing “Random” can restart the track you’re already listening to — this will happen 1 percent of the time you press the “Random” button.

For example, if you started on track 73, and you pressed the buttons in the sequence “Random, Next, Random, Random, Next, Next, Random, Next,” you might get the following sequence of track numbers: 73, 30, 31, 67, 12, 13, 14, 89, 90. You always know the number of the track you’re currently listening to.

Your goal is to get to your favorite song (on track 42, of course) with as few button presses as possible. What should your general strategy be? Assuming you start on a random track, what is the average number of button presses you would need to make to reach your favorite song?

(fivethirtyeight)

Solution

Let $R$ be our answer: the number of expected presses if you start at a random song. If you are listening to a track that is a number $i$ Next-presses from your favorite, then if $i$ is sufficiently low, you should hit Next until you reach it, expecting with certainty $i$ presses. Otherwise you hit Random, expecting $R$ presses after that, or $R+1$ in total.

Let $k$ be your strategic threshold: the greatest $i$ such that you will hit Next when you can reach your favorite with exactly $i$ Next-presses. A random song has probability $(k+1)/100$ of being in the hit-Next group, with an average of $k/2$ presses needed to reach your favorite. And it has probability $(99-k)/100$ of being in the hit-Random group, with an average of $R+1$ presses needed. Therefore:

\[R = \frac{k+1}{100} \cdot \frac{k}{2} + \frac{99-k}{100} \cdot (R+1)\]

Solving,

\[R = \frac{k}{2} + \frac{99-k}{k+1}\]

This function of $k$ has its minimum value when $k$ is $10\sqrt{2}-1$, which is just over $13$. Therefore, we choose $k = 13$, and $R$ is $177/14$ or about $12.64$ button-presses.