PDA

View Full Version : How random is Random Song Mix?



Mike Anderson
2006-01-03, 22:13
I'm curious how random the "Random Song Mix" feature is. Is it truly (pseudo)random?

I ask this because I frequently find that a random mix will select two songs off the same album within a short span of songs, even though I have quite a few albums (more than 600).

I haven't done any statistical testing to detect any non-randomness, but I suspect there's something going on.

ezkcdude
2006-01-03, 22:22
If you want a great randomizer, try Music Magic.

kdf
2006-01-03, 22:35
On 3-Jan-06, at 9:13 PM, Mike Anderson wrote:

>
> I'm curious how random the "Random Song Mix" feature is. Is it truly
> (pseudo)random?
>
> I ask this because I frequently find that a random mix will select two
> songs off the same album within a short span of songs, even though I
> have quite a few albums (more than 600).
>
> I haven't done any statistical testing to detect any non-randomness,
> but I suspect there's something going on.
>
From Slim/DataStores/DBI/Datamodel:

our %sortRandomMap = (

'SQLite' => 'RANDOM()',
'mysql' => 'RAND()',
);

The above is what slimserver uses to draw up a random order for song
selection.
If you have a problem with the randomness, you might have to take this
one up with Larry Wall :)

-kdf

kdf
2006-01-03, 22:36
On 3-Jan-06, at 9:22 PM, ezkcdude wrote:

>
> If you want a great randomizer, try Music Magic.
>
ironically, not at all random :)
just good mixing
-kdf

JJZolx
2006-01-03, 22:42
I'm curious how random the "Random Song Mix" feature is. Is it truly (pseudo)random?

I ask this because I frequently find that a random mix will select two songs off the same album within a short span of songs, even though I have quite a few albums (more than 600).

I haven't done any statistical testing to detect any non-randomness, but I suspect there's something going on.
Why would that be at all surprising to get two songs from the same album within a "short span"? You'd need a lot more intelligence than just randomization to avoid it.

Then again, you could be onto something. There have been inumerable bad attempts at implementing shuffling algorithms that don't give even distributions. It can be a surprisingly difficult "simple" problem.

Interesting Read: http://cigital.com/papers/download/developer_gambling.php

Marc Sherman
2006-01-04, 06:46
Mike Anderson wrote:
>
> I ask this because I frequently find that a random mix will select two
> songs off the same album within a short span of songs, even though I
> have quite a few albums (more than 600).

That's essentially the Birthday problem. It's not a problem with Random
Mix, but rather with your understanding of statistics, probably
compounded by the fact that you tend to notice it when it happens, but
ignore the situation when it doesn't, making it seem like it happens
even more frequently than it really does.

- Marc

ezkcdude
2006-01-04, 08:31
Mike Anderson wrote:
>
> I ask this because I frequently find that a random mix will select two
> songs off the same album within a short span of songs, even though I
> have quite a few albums (more than 600).

That's essentially the Birthday problem. It's not a problem with Random
Mix, but rather with your understanding of statistics, probably
compounded by the fact that you tend to notice it when it happens, but
ignore the situation when it doesn't, making it seem like it happens
even more frequently than it really does.

- Marc


Exactly. For example, one could ask the complementary question, "Why don't I hear two songs from the same album that often?"

As for the Music Magic, I should have said "It's a great non-randomizer".

Mike Anderson
2006-01-04, 09:37
That's essentially the Birthday problem. It's not a problem with Random Mix, but rather with your understanding of statistics, probably compounded by the fact that you tend to notice it when it happens, but ignore the situation when it doesn't, making it seem like it happens even more frequently than it really does.

- Marc

Well it isn't a problem with my understanding of statistics; I have a masters in statistics from UC Berkeley! And I already know this is a Birthday problem.

Like I said, I haven't actually calculated any p-values yet , it's just my judgment so far. But it's easy to calculate p-values, so I'll do so as soon as I get a chance, maybe this weekend.

Mike Anderson
2006-01-04, 09:41
From Slim/DataStores/DBI/Datamodel:

our %sortRandomMap = (

'SQLite' => 'RANDOM()',
'mysql' => 'RAND()',
);

The above is what slimserver uses to draw up a random order for song
selection.
If you have a problem with the randomness, you might have to take this
one up with Larry Wall :)

-kdf

Can I assume it samples (with replacement, over a uniform probability function) songs at random from the list of all songs, such that an album with twice as many songs as another is twice as likely to be selected in any given draw?

Dan Sully
2006-01-04, 09:55
* Mike Anderson shaped the electrons to say...

>> 'SQLite' => 'RANDOM()',
>> 'mysql' => 'RAND()',
>> );
>
>Can I assume it samples (with replacement, over a uniform probability
>function) songs at random from the list of all songs, such that an
>album with twice as many songs as another is twice as likely to be
>selected in any given draw?

I'm not sure what you can assume. The randomizing asks the database driver
for a "random" selection of rows. The goal here was speed - and as few
fetches from the DB as possible.

If someone would like to refactor this to be properly random, and perhaps
without repeats given a certain sample size - patches welcome. :)

-D
--
<noah> I used to be indecisive, but now I'm not sure.

ezkcdude
2006-01-04, 10:23
I'm sure it's as random as most pseudo-randomizers are. Why would they have gone to greater length to make it not-so-random? It's probably a lot more work to do that. I would guess if there is a problem, it's with the "random" number generator.

Edit: It's funny that this issue also comes up frequently on the Apple forums. People always seem to think iTunes playlists are not really random (as random as pseudo-random can be, obviously). I would seriously suggest, having just purchased the product myself, that people check out Music Magic. It's not random (more like random++, actually), but it is a much better way of listening to your library when you don't feel like completely random, but are too lazy to make specific playlists.

Marc Sherman
2006-01-04, 10:53
Mike Anderson wrote:
>
> Well it isn't a problem with my understanding of statistics; I have a
> masters in statistics from UC Berkeley! And I already know this is a
> Birthday problem.

Heh. Sorry about that.

- Marc

Mike Anderson
2006-01-04, 19:08
I'm not sure what you can assume. The randomizing asks the database driver for a "random" selection of rows. The goal here was speed - and as few fetches from the DB as possible.


Does one row correspond to one song? And do you know if it samples with replacement? (I would assume the answer to the latter is "yes", because I *think* I've seen the same song twice in a randomly generated list before.)

JJZolx
2006-01-04, 19:40
Does one row correspond to one song? And do you know if it samples with replacement? (I would assume the answer to the latter is "yes", because I *think* I've seen the same song twice in a randomly generated list before.)
You're talking about the Random Mix plugin, correct? Given the way the Random Mix plugin operates - by placing N items into the playlist, then when on has played, selecting another, I wouldn't be surprised if it does a very simple random selection "with replacement". The plugin author would have to answer this question.

I suppose a better method would be to do a random ordering of all tracks that meet the selection criteria, hold that list in memory, and feed them one-by-one into the playlist. But that's a very memory intensive way of doing it when you have a large database.

A less memory-intensive method, a random select _without_ replacement, would be to keep a list of tracks that have already been selected and exclude them from the random query for the next track. In SQL, this is easily done with a NOT IN ({set of track_id}) in the WHERE clause, although this gets pretty expensive when that set grows large.

mcw
2006-01-05, 03:26
You're talking about the Random Mix plugin, correct? Given the way the Random Mix plugin operates - by placing N items into the playlist, then when on has played, selecting another, I wouldn't be surprised if it does a very simple random selection "with replacement".

I believe it's hard to get a pseudo random number generator to produce a sequence without patterns.

For example, I wrote a perfect shuffle in perl for Winamp .m3u playlists - nothing of releasable quality as far as I'm concerned - but just for my own use, because I wasn't happy with Winamp's.

The shuffle should be "perfect" - given a perfect random feed, but actually it still biases towards certain tracks etc.

I know this because - as with winamp (and I expect the random plugin on slimserver once I've been using it for a while) - you start to notice that it's leaning towards some parts of the collection - and when you move things around by adding music that all changes and you get a fresh feel to the "random" playlists for a while.

So it's not so easy as it sounds to get a satisfying random feed of music (perhaps one that biases a little towards tracks it hasn't played recently would be a good compromise?).

Cheers,

Mark

kweller
2006-01-05, 04:02
In article <mcw.215q80 (AT) no-mx (DOT) forums.slimdevices.com>, Mcw wrote:
> So it's not so easy as it sounds to get a satisfying random feed of
> music (perhaps one that biases a little towards tracks it hasn't played
> recently would be a good compromise?).

...and one that biases towards tracks with higher ratings would be nice :)

Kevin

JJZolx
2006-01-05, 10:13
I believe it's hard to get a pseudo random number generator to produce a sequence without patterns.
I'm not talking about random number generators. I'm talking about the behavior of the Random Mix plugin. Because of the way it operates:

- Pick N random songs (I forget the default number - 10?)
- Play one
- Add one, so there are still N in the playlist

It's the last part that is easy to screw up. It's probably doing selection with replacement, as Mike suggested. So it can easily replay the same song in the same session. Perhaps even back-to-back. It wouldn't be difficult to keep track of what's been played, so that it doesn't play again, but I don't know if the database capabilities offered to plugins by SlimServer are up to that sort of thing.

max.spicer
2006-01-06, 11:45
The RandomMix plugin currently takes no steps to avoid playing the same track more than once. However, I've started work on a change to stop songs being played more than once using the last played timestamp (http://bugs.slimdevices.com/show_bug.cgi?id=2551). This will get done, but I'm still recovering from the Christmas period atm so am spending very little time on Slim stuff.

Max


You're talking about the Random Mix plugin, correct? Given the way the Random Mix plugin operates - by placing N items into the playlist, then when on has played, selecting another, I wouldn't be surprised if it does a very simple random selection "with replacement". The plugin author would have to answer this question.

I suppose a better method would be to do a random ordering of all tracks that meet the selection criteria, hold that list in memory, and feed them one-by-one into the playlist. But that's a very memory intensive way of doing it when you have a large database.

A less memory-intensive method, a random select _without_ replacement, would be to keep a list of tracks that have already been selected and exclude them from the random query for the next track. In SQL, this is easily done with a NOT IN ({set of track_id}) in the WHERE clause, although this gets pretty expensive when that set grows large.

kweller
2006-01-06, 11:56
In article <max.spicer.21881b (AT) no-mx (DOT) forums.slimdevices.com>, Max.spicer
wrote:
> The RandomMix plugin currently takes no steps to avoid playing the same
> track more than once. However, I've started work on a change to stop
> songs being played more than once

Are you going to make that an option? I have mine on random mix pretty
much permanently so want tracks to come up more than once.

Kevin

geoffb
2006-01-06, 12:34
On 1/6/06, Kevin Weller <SlimDML (AT) thewellers (DOT) net> wrote:
> In article <max.spicer.21881b (AT) no-mx (DOT) forums.slimdevices.com>, Max.spicer
> wrote:
> > The RandomMix plugin currently takes no steps to avoid playing the same
> > track more than once. However, I've started work on a change to stop
> > songs being played more than once
>
> Are you going to make that an option? I have mine on random mix pretty
> much permanently so want tracks to come up more than once.

The last-played timestamp is a great solution, since it would
presumably let you make an option that said "don't choose items played
in the last n minutes". That said, does the timestamp also include
the player identifer? If not, then it sounds like multiple players
will screw this up. Especially if player one is cherry-picking all
the 'good' songs, and player two is putting together a random playlist
that can't then include the 'good' songs.

Cheers
Geoff

lemppari
2006-01-06, 12:38
In article <max.spicer.21881b (AT) no-mx (DOT) forums.slimdevices.com>, Max.spicer
wrote:
> The RandomMix plugin currently takes no steps to avoid playing the same
> track more than once. However, I've started work on a change to stop
> songs being played more than once

Are you going to make that an option? I have mine on random mix pretty
much permanently so want tracks to come up more than once.

Kevin

Please make it an option. I like the current way of randomness... :-) Otherwise it is just scrambled playlist.

Kari

JSanchez
2006-01-06, 12:43
As an interesting sidenote, this was brought up a while back in a forum about the Phatbox. The Phatbox exhibits the peculiar behavior of playing the exact same songs in random mode both forward and back. For example if I started on song 10 of 100, then then next song in random mode would always be 20 of 100, etc...likewise if I had started on song 10 then go to 20, hitting the back button would bring me back to song 10. The developers explained how they generated the next track - I believe they read a value from the accumulator and added a value to that - but that's from vauge memory.

Is the Squeezebox random in both directions? I haven't tried that mode yet (just got the thing working yesterday!)

smc2911
2006-03-15, 03:06
...I frequently find that a random mix will select two songs off the same album within a short span of songs, even though I have quite a few albums (more than 600)...
Despite having a mathematics degree, I too was initially suckered by the birthday paradox and was surprised by the frequency of multiple tracks from a single album in a random playlist. To recover my pride, since someone mentioned the birthday paradox (http://en.wikipedia.org/wiki/Birthday_paradox), I could resist doing the calculations. Here are some probabilities for seeing at least two tracks from the same album (any album, not a particular album) for a collection of 350 albums (my collection) and 650 (Mike's).

350 albums, playlist with
assuming replacement (individual tracks may repeat)

10 tracks, probability 12.2%
20 tracks, probability 42.5%
30 tracks, probability 72.2%
40 tracks, probability 90.1%

650 albums, playlist with
10 tracks, probability 6.7%
20 tracks, probability 25.6%
30 tracks, probability 49.3%
40 tracks, probability 70.6%

and assuming no replacement (individual tracks do not repeat in the random playlist), and assuming 10 tracks per album,

350 albums, playlist with
10 tracks, probability 11.0%
20 tracks, probability 39.3%
30 tracks, probability 68.5%
40 tracks, probability 87.7%

650 albums, playlist with
10 tracks, probability 6.0%
20 tracks, probability 23.4%%
30 tracks, probability 45.8%
40 tracks, probability 66.9%

Note that the fewer tracks per album, the lower these probabilities.

Anyone who is inclined to do their own calculations and has a copy of R (http://www.r-project.org) can use the following code to calculate the "collision probability":

collision <- function(albums, playlist, tracks = 10, replacement = TRUE) {
n <- albums
t <- tracks
k <- playlist
if (replacement)
1 - exp(lfactorial(n) - lfactorial(n-k) - k*log(n))
else
1 - exp(k*log(t) + lfactorial(n) + lfactorial(n*t-k) - lfactorial(n-k) - lfactorial(n*t))
}

Apologies for being a bit of a dag.

max.spicer
2006-03-15, 11:13
So do you conclude that there is or is not any statistical evidence that the random mix isn't being random?

Max


Despite having a mathematics degree, I too was initially suckered by the birthday paradox and was surprised by the frequency of multiple tracks from a single album in a random playlist. To recover my pride, since someone mentioned the birthday paradox (http://en.wikipedia.org/wiki/Birthday_paradox), I could resist doing the calculations. Here are some probabilities for seeing at least two tracks from the same album (any album, not a particular album) for a collection of 350 albums (my collection) and 650 (Mike's).

smc2911
2006-03-15, 13:25
I'd conclude that even with a large album collection there's a surprisingly high chance of two tracks (or more) from the same album coming up in a relatively short random mix. Because this is somewhat counter-intuitive and, as someone else noted, we tend to notice it when it happens and not all the times that it doesn't, the natural reaction is to conclude that the mix is not very random. My conclusion is that the (pseudo) random mix is likely to be fine and it's our intuition that's awry.

Sean.

Mike Anderson
2006-03-15, 20:41
I'd conclude that even with a large album collection there's a surprisingly high chance of two tracks (or more) from the same album coming up in a relatively short random mix. Because this is somewhat counter-intuitive and, as someone else noted, we tend to notice it when it happens and not all the times that it doesn't, the natural reaction is to conclude that the mix is not very random. My conclusion is that the (pseudo) random mix is likely to be fine and it's our intuition that's awry.

Sean.

I understand your logic, but one would have to conduct an empirical test to be sure. The problem is that having a different number of songs on each album makes the empirical test somewhat more difficult to conduct.

I know how to compute a p-value, to be sure, but I just don't have the time to do it right now. Perhaps one of these days, when I don't have something a million times more important on my plate, I'll try it. That should happen in about, oh, ten years or so.

Of course I raised the initial question, so I'm to blame.

smc2911
2006-03-16, 14:59
Ahh to have more time! It is easier though assuming sampling with replacement as the number of tracks on each album is then irrelevant, only the number of albums comes into play.

EDIT: I'm actually wrong here. If all the albums have the same number of tracks, it doesn't matter how many tracks there are (when there's replacement), but if albums have different numbers of tracks (which they apparently do in the real world), things get much trickier. My guess is that if the variation in track number is small compared to the number of albums, there shouldn't be too much of a difference.