martinshuffle.txt

gistfile1.txt

Let's say the cost to shuffle is C1 and the cost to press next/previous is C2,

Consider the space of songs as a continuous interval of length L.
Then the task is to select a strategy parameter r that defines the
radius of attraction: when you get within distance r, you switch to
using next and previous to converge to the target. 

Dimensional analysis solution:

The relevant constants are C1, C2 and L, and r is an unknown parameter
to be expressed in terms of these guys. L and r both have units of
distance, C1 has units of time / trial and C2 has units of time /
distance / trial.  If L, C1 and C2 must all be used in the expression
for r then in particular the units on both sides of the defining
equation must balance. The main constraint is killing the time and
trial units that come from C1 and C2. The most obvious way is to
simply divide them out, leaving distance. If r has the form

    r = K L^a (C1/C2)^b

for some dimensionless constant K, unit consistency tells us that

    distance = distance^a distance^b = distance^(a+b)

and so a + b = 1. That doesn't leave us with a unique solution: we
have one unknown too many. But as we expect there to be a unique
solution in the underlying problem, the trick of the trade is guess a
particularly symmetric form to reduce the degrees of freedom. In this
case the obvious symmetry is a = b. That implies a = b = 1/2, which
means r is proportional to

    sqrt((C1/C2) L)

Calculus solution:

The total expected cost is

    C1 * (expected number of shuffles before landing in the basin of
attraction) + C2 * (expected number of next/previous presses,
conditional on having landed in the basin of attraction)

If it is assumed a priori that r will be relatively small in scale
compared to L then edge effects can be ignored and every song has a
basin of attraction of length 2r. The probability of a given shuffle
outcome landing in the basin of attraction for a given song is
therefore p = 2r/L. This defines a binomial process, which has 1/p =
L/2r as its expected number of failures before a success. That takes
care of the first term.

For the second term, the expected number of next/previous presses is
the discrete analogue of the average central distance of points within
radius r of a point. This is

    1/2r integral(-r, r) |x| dx =
    2/2r integral(0, r) x dx =
    1/r (1/2 r^2) =
    1/2 r

The total expected cost as a function of r is thus

    C(r) = (1/2 * C1 * L) 1/r + (1/2 * C2) r

To find the minimum, differentiate C, set equal to zero and solve for
r. The derivative is

    C'(r) = (-1/2 * C1 * L) 1/r^2 + 1/2 * C2

and therefore

    r = sqrt((C1/C2) * L)