How Fast Can You Skip To Your Favorite Song?

Riddler Express

On the planet Jakku (radius $4{,}000$ miles), the droid BB-8 must reach Rey, whose location is uniformly random on the surface. BB-8 rolls at $3$ miles per hour. Even knowing where Rey is, what is the probability BB-8 could reach her within $24$ hours?

The Riddler, FiveThirtyEight, December 6, 2019(original post)

Solution

In $24$ hours BB-8 can travel $3 \times 24 = 72$ miles, so it can reach any point within $72$ miles of its start. Rey is reachable exactly when she lies in that small cap of the surface. The probability is the cap’s area divided by the whole surface. Over such a tiny radius the surface is essentially flat, so the cap is a disk of radius $72$ miles, area $\pi (72)^2$, against the sphere’s area $4\pi (4000)^2$: $$\frac{\pi \cdot 72^2}{4\pi \cdot 4000^2} = \frac{5184}{64{,}000{,}000} \approx \boxed{0.0081\%},$$ about one chance in $12{,}000$. Accounting for the sphere’s curvature changes this only in the sixth decimal place (to $0.0080998\%$): the reachable patch is minuscule, which is why finding Rey is so hard.

The computation

Encode the area ratio, both with the flat-disk approximation and with the exact spherical cap (area $2\pi R^2(1 - \cos\theta)$ for angular radius $\theta = 72/4000$), to show they agree to four significant figures.

import math
R, reach = 4000, 72
flat = math.pi * reach**2 / (4 * math.pi * R**2)
theta = reach / R                                   # angular radius (radians)
cap = 2 * math.pi * R**2 * (1 - math.cos(theta)) / (4 * math.pi * R**2)
print(f"flat   {100 * flat:.4f}%")
print(f"curved {100 * cap:.7f}%")
# flat   0.0081%
# curved 0.0080998%

Riddler Classic

A playlist has tracks $1$ to $100$. “Next” moves to the next track (wrapping $100 \to 1$); “Random” jumps to a uniformly random track (possibly the current one). Starting on a random track, you want to reach track $42$ in as few presses as possible. What is the best strategy, and the average number of presses?

The Riddler, FiveThirtyEight, December 6, 2019(original post)

Solution

“Next” is great when you are just short of $42$; “Random” is the escape hatch when you are far away. So the strategy is a threshold: press “Next” if you are within $k$ tracks before $42$, otherwise press “Random” and try again. The only question is the cutoff $k$.

Suppose you use cutoff $k$ and let $B$ be the average number of presses from a random start. With probability $\tfrac{k+1}{100}$ your start is already within $k$ of $42$ (the $k+1$ tracks $42-k, \ldots, 42$), needing on average $\tfrac{k}{2}$ Next-presses. Otherwise you press Random once and are back to a random track, expecting $B$ more presses. So $$B = \frac{k+1}{100}\cdot\frac{k}{2} + \frac{99-k}{100}\,(1 + B) \;\Longrightarrow\; B = \frac{k}{2} + \frac{99-k}{k+1}.$$ Minimising over whole $k$ gives $k = 13$ and

The balance is intuitive: Next alone wastes presses crawling across the whole list, Random alone keeps overshooting, and the hybrid spends a Random press only until it lands in the short home stretch.

The computation

Encode it two ways: the threshold formula $B(k) = \tfrac{k}{2} + \tfrac{99-k}{k+1}$ minimised over $k$, and an independent value iteration on the $100$-track Markov decision process (each state’s value is one press plus the cheaper of Next and the Random average). They should agree.

# threshold formula
k, B = min(((k, k/2 + (99 - k)/(k + 1)) for k in range(100)), key=lambda t: t[1])
print(f"formula: k={k}, B={B:.3f}")

# value iteration on the full MDP (Random may restart the current track)
V = [0.0] * 101
for _ in range(100000):
    rand = sum(V[1:101]) / 100                      # value of pressing Random
    new = [0.0 if s == 42 else 1 + min(V[s % 100 + 1], rand) for s in range(101)]
    if max(abs(a - b) for a, b in zip(new[1:], V[1:])) < 1e-12: V = new; break
    V = new
print(f"MDP: average presses = {sum(V[1:101]) / 100:.3f}")
# formula: k=13, B=12.643
# MDP: average presses = 12.643

Both give a cutoff of $13$ and about $12.6$ presses on average.