I was messing with the Tweak Order functions today and I think there's something fishy going on. I've noticed this before (for many versions, ever since tweak order was introduced), but couldn't really put my finger on anything concrete enough for an official report until now.

This isn't a big deal. For example, it shouldn't hold up the public release of 1.01 or anything, which is why I'm posting it here instead of telling empeg about it directly.

Okay. Here's the setup: I'm playing my "low key" playlist, shuffled. Somewhere at the beginning of the playlist, it played the song "Travels" by Pat Metheny, from his most recent "Trio 99-00" album.

Later (about 30 songs into the playlist according to the little number on the now/next screen), another song from the "Trio 99-00" album appears, in this case, the song was called "We Had a Sister". At that moment, I decided I wanted to hear "Travels" again.

But I didn't want to restart the playlist or anything. I didn't even want the current song to stop, I just wanted the next song in the shuffle to be "Travels". And since we don't have an "Insert by title" function yet, I thought I'd use Tweak Order to get what I was after.

So I pressed "3" on the remote, to have it find "Matching Source", which it did dutifully, and found another song from "Trio 99-00" (I think I have three or four songs from that album in that playlist).

It wasn't the song I wanted, though, it wasn't "Travels". So I pressed 8 to make it randomly swap the next song. Then I pressed 3 again. The idea in my head is that, after a couple of 8/3 presses, my desired song would drop into the next slot. I mean, if I've only got three or four songs from that album in this playlist, it shouldn't take that many re-swaps to make it appear.

But it never appeared. Every time, I got the same undesired song from that album.

So I thought, Hmm. Instead of pressing "8" first, I just pressed "3" a second time to force it to pick something other than the undesired song. It said it couldn't find any matching source. But I know that playlist had at least one other song from that album, because I'd just heard it a few songs ago.

Here's my theory: When you do "Tweak Order", it only picks from the remainder of the current playlist, not from the entire playlist. Since I'd already passed "Travels" in the playlist, it never went hunting for it.

Okay, so to summarize: Problem 1: Tweak Order only picks from what's left of the current playlist.

Onto my other problem:

The "8/3" stunt I described above is generally my way of working around the lack of an "Insert by title" feature for now. There have been times when I've used it successfully while playing a huge shuffled playlist (the root playlist of the whole player).

However, when I use that 8/3 stunt, it takes way more tries to get the desired song than it should, and it has a tendency to pick the same song over and over again. For instance, if it's currently playing "YYZ" and I want the next song to be "Limelight", I should expect to hit 8/3 about 6 to 12 times before it comes up properly. But instead of all of the Moving Pictures tracks coming up randomly in that next slot, it tends to keep dropping the same song into the next slot (for example, "Witch Hunt"). It could take me 30 tries to get it to drop "Limelight" into the slot, 25 of which came up with the same result every time.

So, in summary. Problem 2: Tweak Order doesn't randomize hard enough when you ask it to find you another song.

This might be related to something I've noticed, separate from the Tweak Order functions, which is that I don't think the unit is randomizing very hard to begin with. For instance, when I shuffle the whole unit, I get a lot more "two-fers" and "three-fers" than I'd expect by chance. It's taken me months of listening to come to this conclusion, so it's very subtle. But what are the odds that this is the case? How's the code work for randomizing the actual de-duped playlists?

___________
Tony Fabris

<pedant>If the tracks from the same album never occurred next to eachother, it wouldn't be random, would it?</pedant>

In short, the STL libraries that come with gcc don't have a particularly good implementation of shuffle. We (IIRC) run it a couple of times in an attempt to get good effects, but even so...



Roger - not necessarily speaking for empeg

Problem 1: Tweak Order only picks from what's left of the current playlist.

Yes, we rather carefully designed it to do that. Surely most of the time this behaviour is what you want -- it wouldn't be hard to change, but I don't think people would like it.

If there's a specific song you want to hear again, why not just go and find it from the menu, or search for it?

Hmm, on thinking a bit more, I guess your answer will be that you don't want to lose your place in the playlist. In version 1.1, bookmarking will help with that (as will much smarter random play in the first place).

Perhaps what's really required is a third mode for searching: append after current track (rather than add at end of playlist, or replace playlist)...

Problem 2: Tweak Order doesn't randomize hard enough when you ask it to find you another song.

Now this sounds more like a real bug. I'll look into it...

Peter

Perhaps what's really required is a third mode for searching: append after current track (rather than add at end of playlist, or replace playlist)...

This is planned, but there are UI issues to be addressed. The current mechanism for switching between select and append is incredibly confusing and limited in scope. We need a global setting that affects playlist selection from the main menu too so you can select a playlist for append, insert or replace.

Actually implementing it isn't hard at all.


--
Mike Crowe
I may not be speaking on behalf of empeg above :-)

append after current track (rather than add at end of playlist, or replace playlist)...
This is planned

Mike, you're my new best friend.

___________
Tony Fabris

Yes, we rather carefully designed it to do that. Surely most of the time this behaviour is what you want -- it wouldn't be hard to change, but I don't think people would like it.

Hmm. I guess you're right. The only reason I needed to have it the other way around is because we don't yet have an "Insert" option for search results. I was using it as a work-around for the lack of an upcoming feature.

Carry on.

___________
Tony Fabris

Randomization shouldn't be that hard. An order N algorithm is provably random. Here's one a friend of mine coded up...it takes a pointer to a list of integers and the size of the list, then builds that list and shuffles it. You should never need to shuffle more than once. I have not included a proof. ;)

void shuffled_ramp(int *pos, int size)
{
    /* build a ramp, for shuffling */
    for (int i = 0; i < size; i++)
        pos = i;
    for (int i = 0; i < size; i++)
    {
        int r = random() % (size - i);
        int tmp = pos;
        pos = pos[r + i];
        pos[r + i] = tmp;
    }
}

I encourage you to try it out. And if this shows up as preformatted, I don't know why, as I've included an end tag..

Fly me to the moon...

An order N algorithm is provably random. Here's one a friend of mine coded up...

This is essentially the same shuffle algorithm that the STL uses. The problem is not in the shuffle algorithm, it's in random().

Peter

It could also depend on when & how the random library is seeded.

Mk2/40GB/Blue

Ach, that sucks. I'm not familiar with linux on the arm, does /dev/random do what it's supposed to? Have you tried any different randomization libraries?


Fly me to the moon...

the STL libraries that come with gcc don't have a particularly good implementation of shuffle.

I can offer some empirical evidence of this... I just had three out of a group of four songs come from the same playlist in a full shuffle of the entire empeg and I have over 160 playlists containing a total of 1449 tracks..

tanstaafl.

"There Ain't No Such Thing As A Free Lunch"

I can offer some empirical evidence of this... I just had three out of a group of four songs come from the same playlist in a full shuffle of the entire empeg and I have over 160 playlists containing a total of 1449 tracks.

While it's certainly the case that there are deficiencies in the shuffle algorithm, I have to point out that your example isn't really empirical evidence of anything. :) I mean, I have over 3000 tracks, and occasionally I have 2 tracks in a row (or 3 out of 4) come from the same playlist - but you'd expect this to happen sometimes in a random shuffle; it's no more or less likely than any other set of 3 or 4 songs coming up in sequence.

Now, if the shuffle were a two-tiered algorithm, where it shuffled "playlists" to get a sequence of playlists to pick tracks from, and then picked the actual tracks from those playlists in another random draw, it'd become less likely to have multiple songs from the same playlist close together; but still possible, of course, unless the algorithm actually took steps to guarantee that that didn't happen. But then you're imposing structure on the random ordering ("the same playlist can't be chosen twice without at least N playlists being chosen in between"), which in and of itself will make it less random/more predictable. Something like this, as I understand it, is being done on a per-track basis for 1.1 (tracks which have been played less often have a better chance of popping up earlier in a shuffle - correct?), but that still doesn't do anything about your example.

You can't really win; except by getting a good source of randomness in the first place and sticking to it. Easier said than done, of course. :)

-Dan

-----
Daniel M. Zimmerman
Mk.2 #060000058, 36GB, Red
Mk.1 #00101, 10GB, Blue

your example isn't really empirical evidence of anything. :)

Of course, you are correct. Point well taken.

But you know what I meant, though... the probability of three tracks out of a random four being from the same playlist (out of 165 playlists total) is pretty low given the assumption of true randomization. I am pretty weak when it comes to the mathematics of probability, but it seems to me that the likelihood of this happening is about 1 chance in 27,000. Of course, I'm probably wrong about this, too.

I'll betcha that you could show me the math involved in calculating this, though, and I'd enjoy seeing it.

tanstaafl.



"There Ain't No Such Thing As A Free Lunch"

I'll betcha that you could show me the math involved in calculating this, though, and I'd enjoy seeing it.

Seriously? I definitely could, but I'd need to know all the variables (such as how big each playlist is - if we're trying to calculate the actual probability of getting 3 out of 4 tracks all from the same playlist, we need to know how big every playlist is - it's much more likely to happen with a 100 track playlist than, say, a 2 track playlist). It'd be a big, messy calculation.

More generally, though, if we want to just pick 3 particular tracks out of N tracks on the player, and say how likely it is that we see those 3 tracks in a given random set of 4, the calculation is much easier:

(N-3)/N * 3/(N-1) * 2/(N-2) * 1/(N-3) +
3/N * (N-3)/(N-1) * 2/(N-2) * 1/(N-3) +
3/N * 2/(N-1) * (N-3)/(N-2) * 1/(N-3) +
3/N * 2/(N-1) * 1/(N-2)

If N is your aforementioned 1449 tracks, this gives us a probability of about 7.9x10^-9, or 1 in 126501081. Very improbable. :)

But of course, doing the calculation for playlists is very different, and adds all sorts of correlations which aren't there if we choose 3 random tracks and then 4 random tracks, and see if our 3 are contained in our 4.




-----
Daniel M. Zimmerman
Mk.2 #060000058, 36GB, Red
Mk.1 #00101, 10GB, Blue

I thought it was seeded from /dev/urandom at startup (obviously we can't use /dev/random unless you want to sit randomly pressing buttons at startup before it wakes up).

Maybe we ought to reseed it before each shuffle operation. I'll look into it.

--
Mike Crowe
I may not be speaking on behalf of empeg above :-)

I'll betcha that you could show me the math involved in calculating this, though, and I'd enjoy seeing it.

OK, you asked for it.

Suppose you're playing one of your 1449 tracks. The chance that the next track will also come from the same one of your 160 albums is 1/160. The chance that the one after will too, is another 1/160 [*]. So, for each of the 1449 tracks in the playlist, the chance that it'll be the start of a run of three from the same album is 1/(160*160).

The chance of this happening somewhere in the playlist of 1449 tracks is thus 1449*1/(160*160) [*] or about 5.7%.

But the original event wasn't three in a row, it was three out of four. The probability of the fourth track not being from that album, is 159/160 [*]. So the chance of three in a row from the same album followed by the fourth not being from that album is 159/(160*160*160). But to find the probability of "three out of four", there are four positions the fourth, not-from-the-same-album, track could be in. So the probability of any given track being the start of a run of three-out-of-four is 4*159/(160*160*160).

The chance of this happening at least once in a playlist of 1449 tracks is 1449*4*159/(160*160*160) or about 22.5%.

So it won't happen every time you shuffle, but it's not the end of the world for our randomisation algorithm.

Peter


[*] Ignoring very small second-order terms. For instance, the probability of the next track being from the same album isn't 1/160, it's slightly reduced by the fact you've just played a song from that album, so that not quite 1/160 of the remaining songs are also from that album.

Peter, you don't, by any chance, happen to be a Blackjack player?

___________
Tony Fabris

The chance of this happening somewhere in the playlist of 1449 tracks is thus 1449*1/(160*160) [*] or about 5.7%.

This is where I got my estimate of 27,000 to one (I was using 165 playlists instead of 160) that the chances of a single group of four songs containing three in a row from the same playlist would be 1/(165*165). I hadn't considered that 1449 tracks would contain 1446 groups of four contiguous tracks thus expanding the likelihood of this occurring by a factor of 1446, and of course I didn't consider the "three out of four" part at all.

Note that in absolute desperation to preserve some pretense that I am a little bit knowledgeable, I point out the very small nit-pick in your explanation that the chance of this happening is not 1449*1/(160*160), but 1446*1/(160*160) as there are only 1446 (not 1449) possible groupings of four contiguous songs in the 1449 song total. This of course changes the percentage from 5.66% to a whopping 5.65%. Please, let's make some attempt at accuracy here.

It still seems counter-intuitive that there could be better than a one in 20 chance that a randomly generated playlist (given 160 playlists and 1449 songs) would have three in row from one of the playlists, but there you have it. It is like the "trick" whereby in a room of 30 people the odds are very high that two of them will share the same birthday. I've had this one explained to me but could never quite get my mind around it.

And of course the "three out of four" thing opens up new possibilities as you pointed out.

I'll say it again... we have an extraordinary group of people contributing to this bbs!

Thanks for the math lesson!

tanstaafl

"There Ain't No Such Thing As A Free Lunch"

Peter, by any chance did you graduate from college recently? My theory is the ability to work out probability problems decrease the more time you spend away from college.

Calvin

Just to make it alittle more complicated :
1446 isn't right either.
when I've got 160 playlist with 1449 songs alltogether, this means there's an average of 1449/160=9.05625 songs per playlist.
let's assume 9 playlists with 10 songs and 151 with 9 songs.
in the playlists with 10 songs there are 7 possible combinations and in the ones with 9 songs there are 6
So 9*9 + 151*6 = 987.

The above number is correct under the assumption that there are 9 lists with 10 and 151 lists of 9 songs though.
To be completely accurate you should first find all possible solutions of fitting 1449 songs in 160 playlists, then calculate the number of groups of four they can contain and calculate the average.


Frank van Gestel

I thought the songs would be from the same playlist in the same order, but that isn't clear to me now.
Anyway, the chance that the second song is from the same playlist isn't 1/160 as I could have 159 playlists with 1 song in them and 1 playlist with the rest of them, so you should still count all possibilities of playlists...


Frank van Gestel

OK, you asked for it.

(snip some incorrect probability calculations)

[*] Ignoring very small second-order terms. For instance, the probability of the next track being from the same album isn't 1/160, it's slightly reduced by the fact you've just played a song from that album, so that not quite 1/160 of the remaining songs are also from that album.

In this case, the "very small second-order terms" add up to a whole lot of error, as the probability you came up with (22.5%) is almost 44% higher than the actual probability (15.6%).

The correct calculation works like this:

We're playing a track. It's in one of our 160 playlists. The only way we can reasonably do this calculation is to assume that all playlists are of identical size (as I mentioned earlier, the calculation becomes really difficult if they vary in size). So, let's assume that each of our 160 playlists has (1449/160), or about 9.06, songs.

The chance that the next track will also come from the same playlist is (((1449/160) - 1)/1448); there are (1449/160) - 1 songs left in your playlist, and 1448 left to be chosen from. Similarly, the chance that the track after that will also come from the same playlist is (((1449/160) - 2)/1447).

The chance of this (3 in a row) happening somewhere in the playlist is therefore about 3.92%, when we multiply these 2 probabilities by the 1446 possible positions in a playlist where a sequence of 4 can start.

Now we factor in the 4th song. The probability of the 4th song not being from the same playlist is ((1449 - (1449/160))/1446); there are all the songs except our one playlist to choose from, and 1446 songs left in total. So the probability of 3 in a row from one playlist, followed by a 4th from another playlist, is a long ugly equation which evaluates to a probability of about 3.91%. Not discarding the extra figures, when we multiply this result by 4 (for the 4 different locations the "not like the others" song can go), we get the aforementioned 15.6%.

This calculation, however, is pretty much worthless for figuring out how often this sort of occurrence will happen in the real world, because nobody's playlists are all the same size, and because it's possible (even likely, given the design of the Empeg software) for items to be in multiple playlists. Bottom line, for any practical distribution of songs on an Empeg, I'm pretty sure the only way to calculate this probability exactly is to use brute force. If that's the case (I haven't proven it, of course), given the fact that in this example of 1449 tracks there are more than 1.18x10^3953 permutations to brute-force through, you wouldn't live anywhere near long enough to get the answer. Neither would our universe, probably.

-----
Daniel M. Zimmerman, Caltech Computer Science
Mk.2 #060000058, 36GB
Mk.1 #00101, 10GB

In this case, the "very small second-order terms" add up to a whole lot of error, as the probability you came up with (22.5%) is almost 44% higher than the actual probability (15.6%).

OK, it was bogus of me to quote the result to 3 significant figures. But I still reckon +/- 44% counts as "very small second-order terms" when the object is to refute a calculation that suggests the outcome happens one time in 126,000,000...

Peter

OK, it was bogus of me to quote the result to 3 significant figures. But I still reckon +/- 44% counts as "very small second-order terms" when the object is to refute a calculation that suggests the outcome happens one time in 126,000,000...

I think he had said 1 in 27,000; but you've got a point. While I'd strongly disagree with the phrasing "very small second-order terms", it's definitely the case that those 44% don't matter much for refuting the particular calculation in question. Then again, having something happen 15% of the time is very much different than having it happen 25% of the time (gross rounding there). :)


-----
Daniel M. Zimmerman, Caltech Computer Science
Mk.2 #060000058, 36GB
Mk.1 #00101, 10GB