Shufflin' Like You Mean It

Humans are not known for their keen statistical intuition. We misunderstand variable dependencies, put undue confidence in small observations,and allow our reasoning to be muddled by trivial details. We're not entirely hopeless - we have some basic notions of probability. Most have no problem understanding that if you flip a coin enough times, it will come up heads and tails in roughly equal numbers (in what is known as the law of large numbers). However, this is matched by a mistaken belief in a law of small numbers: that is, we expect small samples to follow a similar distribution to the whole. This overlooks that random chance is well, random - any attempt to figure out a rhythm will be flummoxed by the nature of pure chance.

From an academic perspective this is all well and interesting, but sometimes I find myself desiring a law of small numbers. Now, while I can hardly go out there and force casinos or nature to start abiding by a ruleset that better suits my intuitions, I can, in the privacy of my own home, hope for a methodology that better suites my intuitions in a music queue. A system that still surprises, but paying mind to my innate desire for a degree of evenness in the results.

Developing an Algorithm

Before trying to come up with a solution, it would be good to have a better idea of what, exactly, the problem is. There's no fixed mathematical measure of how "random" something feels, but there still needs to be some loose sense of what the goal is.

One way to conceptualize the problem is to look at the distribution of distance between plays by the same artist. Let's take a look at a simple sample queue - five artists, five tracks apiece.

The above graph shows how often a given gap will occur on a full playthrough of a randomized queue. So, on an average playthough, a track by the same artist will be played back-to-back on average once, a track by the same artist will be broken up by one song about 0.8 times, etc.

From this, a picture of a solution starts to emerge. Small gaps are quite common, and as a side effect there is a very long tail of large gaps between plays. To space out plays, we'd need to concentrate the graph more around the average gap (4) - pull in the long tail, and shift out some of the plays happening in the smaller gaps.

To do this, the randomizer must try to avoid recently played artists, having some sense of memory of recent plays. I fiddled with a few different approaches to this, and settled with the basic principle that after a play by an aritst, the odds that it should reoccur should go down in direct proportion to the fraction of the remaining queue is of that artists. The weighted odds against the artist then decreases with time, returning to it's original state by the time you'd expect another play of the artist to occur.

That explanation was a little thick, so lets break down what happens using the earlier example of five artists, five tracks each. The first track is chosen in a conventionally random fashion - each artist has about a 20% chance of being chosen. Lets say a track by artist A is chosen. The track is played and removed from the queue. Typically, another play from A would typically have a likelihood of 4/24 of occuring, or about a 17% chance.

With the weighting system, the odds are heavily reduced - the chance of reoccurence is "squared", so to speak, leaving an approximate 17% x 17% = 2.9% chance of the artist being played again (the actual math works out a bit differently since the resulting odds have to be normalized, but lets glaze over that).

This weight gradually reduces its impact, going back to the default value by the time another play would be expected. Over the next four plays, the reduction of odds goes from 17% to 21%, 28%, 42%, 85%, then disappears. Of couse, since this merely reduces the odds of the play from happening, another play from an artist can occur before the weight goes away. If this happens, the weights are combined. For example: if a play of the same artist occurs back to back, the weight reduces the odds of another play to just .2%, and will take around 12 plays of other artists before it occurs again.

Putting this to practice, we're left with the following distribution:

Not bad. A noticable improvement over where we started - a back to back play is roughly one half as likey to occur with the new system. Still, that's not quite what I would describe a huge change, hardly fulfilling the radical, life-affirming potential a perfect queue has.

Going back to the part where we "square" the odds an artist will come up again - there's no real reason to limit this to just squaring, really. Rather than multiplying the base chance by .17, why not .17², or .17³, as in the following distribution?-

Quite nice - this looks more like what I was looking for. Back to back plays occurs 80% less than they would in a typical queue. Average distance between plays is tightly clustered around a gap of four, what you'd expect if everything was perfectly spaced.

By altering the degree of the weight, we can get a wide range of possible adjustments from the default state (degree of 0) to the above distribution (degree of 3). Altogether, this gives a powerful way to adjust the frequency of consecutive plays, giving a continuous range to choose from in deciding just how well spaced our queues ought to be -

Performance & Extensions

The performance of this technique is notably worse than a traditional shuffle - a full array of items can be shuffled in O(n) time, while this would take O(n²). Not great, but given the nature of music queues, this is mostly a non-issue.

Queues tend to be pretty small by nature - personally, I doubt I ever break three hundred tracks. Shuffling the entirety of a music library that would fill a 16GB iPod (~3500 tracks) takes less than a second on my machine.

However, you start running into trouble on longer queues. If a music hoarder with tens of thousands of tracks were to be possessed by the need to randomize their entire librarly, they'll see a noticable delay. It's still quite quick to choose a single track to play, but if the user wants a tangible, fully shuffled queue, they'll be in for a wait.

While I'm sure the core perfromance can be improved over my JavaScript implementation, inevitably there's a threshold where things start to break down. There are a few hacks to keep things going - the full list could be normally shuffled, then broken down into more digestible chunks (maybe around ~1000 tracks per chunk). Each chunk could be subjected to the weighted random individually, which could be done much faster than trying to do it all at the same time.

However, I can't help but feel that this would be both unhelpful and a missed opportunity. Having a premade queue for a few hours of music during a party is helpful; a premade queue with months of listening in it, not so much. Besides, massive queues by there nature will include a very diverse set of artists, reducing the odds any single artist will become uncomfortably clustered.

A straight application of the weighted version to a large queue may not be of much help, but some of the principles could be adapted. Trying to perfectly space an artist with that many tracks isn't particularly desirable - with such a large reservoir of music to draw from, an intelligent queue should become more targeted in its decisions. Instead of focusing exclusively on spacing out single artists, you may want to put more emphasis on a different attribute of a track, like genre. This can be done fairly easily - instead of just weighting by artist, the technique can be generalized to allow any number of attributes.

Things can get a bit tricker where the emphasis is less on playing each track individually, and more about passively figuring out what the user wants to hear. You may want favorite artists and recent additions to the library to come up more often than normally, giving each of them a naturally "positive weight". A "negative weight" could still be applied to prevent super-tight clustering, but could be induced to fade quickly to allow the artist/track to come up again soon after (but not too soon). All told, this suggests a bunch of interesting tweaks to be made in the quest for the perfect queue.

For the curious, the source code can be found here. A very basic way to consider multiple weights has been added, but otherwise it's a straightforward implementation of the core algorithm.