From the FiveThirtyEight website: “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?"
I made the assumption that the optimal strategy is to designate, for some integer \(k\), the \(k\) integers from \(42-k+1\) to \(42\) as the range where we will press “Next” until we reach track 42. If we start outside of this range, we press “Random” until we reach it.
According to the geometric distribution, the expected number of “Random” presses to reach the range where we press “Next” is \(\frac{100}{k}\). The expected number of “Next” presses once we reach this range is \(\frac{k-1}{2}\). If we are at the track that is just outside this range, we can reach track 42 in \(k\) “Next” presses, so we want to find the smallest \(k\) such that \(k > \frac{100}{k} + \frac{k-1}{2}\). A little algebraic manipulation shows that this is equivalent to \(k^2+k-200 > 0\). By the quadratic formula, this means that we want the smallest \(k\) that is greater than \(\frac{-1+\sqrt{801}}{2}\), i.e. \(k=14\). So the “Next” range comprises the integers from 29 to 42.
Now we can calculate the expected number of button presses starting at a random track.
(86*(100/14 + 13/2) + sum(0:13))/100## [1] 12.64286As a check on the algebra (and the logic of my criterion for selecting \(k\)), we can also calculate the expected number of presses for each possible of \(k\) and find the smallest.
expectations <- sapply(1:100,function(x) ((100-x)*(100/x + (x-1)/2)+sum(0:(x-1)))/100)
order(expectations)[1]## [1] 14expectations[order(expectations)[1]]## [1] 12.64286For reference, here’s the vector of expected values for each value of \(k\).
names(expectations) <- 1:100
print(expectations)## 1 2 3 4 5 6 7 8
## 99.00000 49.50000 33.33333 25.50000 21.00000 18.16667 16.28571 15.00000
## 9 10 11 12 13 14 15 16
## 14.11111 13.50000 13.09091 12.83333 12.69231 12.64286 12.66667 12.75000
## 17 18 19 20 21 22 23 24
## 12.88235 13.05556 13.26316 13.50000 13.76190 14.04545 14.34783 14.66667
## 25 26 27 28 29 30 31 32
## 15.00000 15.34615 15.70370 16.07143 16.44828 16.83333 17.22581 17.62500
## 33 34 35 36 37 38 39 40
## 18.03030 18.44118 18.85714 19.27778 19.70270 20.13158 20.56410 21.00000
## 41 42 43 44 45 46 47 48
## 21.43902 21.88095 22.32558 22.77273 23.22222 23.67391 24.12766 24.58333
## 49 50 51 52 53 54 55 56
## 25.04082 25.50000 25.96078 26.42308 26.88679 27.35185 27.81818 28.28571
## 57 58 59 60 61 62 63 64
## 28.75439 29.22414 29.69492 30.16667 30.63934 31.11290 31.58730 32.06250
## 65 66 67 68 69 70 71 72
## 32.53846 33.01515 33.49254 33.97059 34.44928 34.92857 35.40845 35.88889
## 73 74 75 76 77 78 79 80
## 36.36986 36.85135 37.33333 37.81579 38.29870 38.78205 39.26582 39.75000
## 81 82 83 84 85 86 87 88
## 40.23457 40.71951 41.20482 41.69048 42.17647 42.66279 43.14943 43.63636
## 89 90 91 92 93 94 95 96
## 44.12360 44.61111 45.09890 45.58696 46.07527 46.56383 47.05263 47.54167
## 97 98 99 100
## 48.03093 48.52041 49.01010 49.50000