#165623 - 14/06/2003 12:37
Re: Strange randomization
[Re: tfabris]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
You got it. Everyone is out from my office next week (getting new work from the client) and all I have to do is answer help calls. At least now I'll get to do some interesting coding!
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165625 - 14/06/2003 12:47
Re: Strange randomization
[Re: tfabris]
|
carpal tunnel
Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
|
I'm sorry if I offend anyone here, but this whole exercise is getting a little ridiculous. The empeg guys have said that their shuffle algorithm is random, even after repeated accusations of bugs and inaccuracies in it. What are you trying to prove with all this hocus pocus you're doing with random number generation and plotting things on graphs and such? What is the end game if you get results that say "the shuffle algorithm isn't as random as it should be." Are you asking them to take yet another look at the code? Do you want to implement some de-combing of related songs after the shuffle is done? I'm not sure I understand the point here. This Delphi program and all the postulates and the hypotheses... What are we after here?
|
|
Top
|
|
|
|
|
#165626 - 14/06/2003 12:53
Re: Strange randomization
[Re: tonyc]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
What is the end game if you get results that say "the shuffle algorithm isn't as random as it should be." Actually, I'm expecting the end game to be "the empeg guys have been right all along, the clustering effects we are noticing are to be statistically expected".
If that's the case, I intend to make a FAQ entry to that effect and link the EXE file as proof for anyone who doesn't believe it.
|
|
Top
|
|
|
|
|
#165627 - 14/06/2003 13:57
Re: Strange randomization
[Re: tonyc]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
I'm not sure I understand the point here. This Delphi program and all the postulates and the hypotheses... What are we after here? My point was to prove the empeg guys right. I'd like to put to bed all of these questions if possible. I was suprised with the outcome of the program (feeling that there were far less "pairs" that I would have expected), but what it was testing wasn't entirely on target. If the analysis Tony F has suggested comes out with "combing", then no one can argue that the Empeg randomizer is bad. If it doesn't, we have further research to do. In the end, I hope we can make this the last discussion on the subject.
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165628 - 14/06/2003 14:40
Re: Strange randomization
[Re: JeffS]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
In-laws visiting this weekend, so I decided to give this a first hack. Haven't really looked at the results, so you can decide what it all means.
Attachments
164030-RandomNumbers.exe (108 downloads)
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165629 - 14/06/2003 14:50
Re: Strange randomization
[Re: JeffS]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
Cool and interesting!
I'm not quite sure how the size of the window relates to the graph. If I change the size of the window, the way the graphed data is laid out changes in ways I don't understand. Can you explain it?
|
|
Top
|
|
|
|
|
#165631 - 14/06/2003 15:27
Re: Strange randomization
[Re: tfabris]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
I'm not quite sure how the size of the window relates to the graph. The width of the blocks are always the same. When you resize the graph, it refigures how many blocks fit on a line, and therefore how to space the lines. So more tracks = more lines = less space between lines. Bigger window = more tracks per line = less lines = more space between lines. Does that help?
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165632 - 14/06/2003 15:33
Re: Strange randomization
[Re: JeffS]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
Yes, it helps. But it makes the graph not very clear, because that means that a large window with only a few lines makes it look like everything is clustered funny. For instance, if there are only ten lines of actual track data, but the window is 50 lines tall, it looks like the tracks are horribly clustered when they really aren't.
Maybe the graph should be a fixed height depending on the number of lines, and let the user change the graph's width by changing the window size. If the graph is too big to fit in the window, put a scroll bar or something.
|
|
Top
|
|
|
|
|
#165633 - 14/06/2003 17:58
Re: Strange randomization
[Re: tfabris]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
I'll see what I can do. The vertical axis shouldn't really be taken into account at all when looking for clustering (and isn't in your above picture), but I understand how it can mess with your perceptions.
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165634 - 14/06/2003 18:24
Re: Strange randomization
[Re: JeffS]
|
Anonymous
Unregistered
|
I saw on tv once about this guy that wrote a program that could figure out a random number generator's algorithm by punching in numbers that it produces and predicting the next numbers. He went to Atlantic City and won the jackpot on some game. Does anyone want to help me write a program like this?
|
|
Top
|
|
|
|
|
#165635 - 14/06/2003 19:09
Re: Strange randomization
[Re: ]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
I had a guy in college who wanted me to write a program to generate lottory picks for him, but he wanted me to make it get rid of the "obvious things that won't come up", such as "1, 2, 3, 4, 5". I told him that was silly, as 1, 2, 3, 4, 5 had the same probability as any other numbers. He just wouldn't listen to me. Finally I took his criteria and wrote him a program that generated the numbers, completely ignorning his "rules". I figured if 1, 2, 3, 4, 5 ever came out I could fix the program then.
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165637 - 14/06/2003 19:51
Re: Strange randomization
[Re: ]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
I saw on tv once about this guy that wrote a program that could figure out a random number generator's algorithm by punching in numbers that it produces and predicting the next numbers. He went to Atlantic City and won the jackpot on some game. This only works with pseudo-random generators. In order for this to have worked for a gambling machine, he'd have to have been (a) playing on a really old machine that used pseudo-random numbers, since all of the new ones use proper random algorithms, and (b) be intimately familiar with the inner code and hardware of the game in question, since the output of a pseudo-random generator is very hardware and code dependent. I seem to recall reading something about this in the documents at http://www.wizardofodds.com , but I don't remember exactly where it was. That's a great site, by the way, if you're interested in information about randomness and probability. I was tempted to consult this guy when we started talking about the car player's shuffle accuracy, but FerretBoy seems to have us covered already. 
|
|
Top
|
|
|
|
|
#165638 - 14/06/2003 20:00
Re: Strange randomization
[Re: ]
|
stranger
Registered: 26/08/2000
Posts: 44
Loc: California
|
Certain pseudorandom number generators (e.g. linear congruential generators) can be reverse-engineered from their output. And for any generator with a small enough seed-space, if you know the generator used you can exhaustively search for the seed which produces the known output. On the other hand, there was a lot of work done on cryptographic generators which are provably as unpredictable as the underlying cipher is uncrackable. And various hardware generators have been proposed whose randomness is guaranteed by quantum mechanics. If I were designing something where real money was riding on the outcome being unpredictable, I'd go for something along those lines.
But for shuffling music, a decent LCG properly used really ought to be good enough.
--John
|
|
Top
|
|
|
|
|
#165639 - 14/06/2003 21:03
Re: Strange randomization
[Re: rompel]
|
carpal tunnel
Registered: 23/08/2000
Posts: 3826
Loc: SLC, UT, USA
|
okay, please excuse my blindness if this has been discussed before (esp. in this thread!), but here's how i'm percieving this whole thing:
1. "People" don't like how the empeg shuffles as it seems to group songs in ways that don't seem "random" enough.
2. In fact, they are truly random, and the grouping is to be expected. And that is what this program is trying to prove.
SO... the question i want to know the answer to, is why would we want a truly random shuffle? Don't we want it to be psuedo-random so that groups and clusters of bands or albums are filtered out, thus making it seem "random"?
|
|
Top
|
|
|
|
|
#165640 - 14/06/2003 21:20
Re: Strange randomization
[Re: loren]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
Yeah, I think that comes under the heading of "wouldn't it be cool if..."
I can think of some ways one might write an algorithm to make something appear more random than truly random, but they all have nasty "gotchas". Like, choosing the lesser of two evils when you've got too much of a given artist on the player: this conflicts with your ability to make other bands appear widely spaced. You end up getting forced to choose who gets a lot of twofers showing up in the shuffle.
Maybe others have already solved this algorithm in cool ways. Perhaps there's some prior art on this that can be referenced...
|
|
Top
|
|
|
|
|
#165641 - 14/06/2003 22:53
Re: Strange randomization
[Re: loren]
|
Carpal Tunnel
Registered: 08/02/2002
Posts: 3411
|
SO... the question i want to know the answer to, is why would we want a truly random shuffle? Don't we want it to be psuedo-random so that groups and clusters of bands or albums are filtered out, thus making it seem "random"?
Hmm. Care to come up with an algorithm for that?!
_________________________
Mk2a 60GB Blue. Serial 030102962
sig.mp3: File Format not Valid.
|
|
Top
|
|
|
|
|
#165642 - 14/06/2003 23:11
Re: Strange randomization
[Re: tfabris]
|
stranger
Registered: 26/08/2000
Posts: 44
Loc: California
|
Maybe others have already solved this algorithm in cool ways. Perhaps there's some prior art on this that can be referenced...
People have done work on something called "quasi-random" sampling in the context of Monte-Carlo integration. The idea is that the integral should converge faster if the sample points are spread out more evenly than would happen by random. Numerical Recipies has a section on the subject or try the following Google searches:
http://www.google.com/search?q=quasi-random
http://www.google.com/search?q=sobol+sequence
http://www.google.com/search?q=halton+sequence
It doesn't really deal with random permutations, but I suspect that if you did a 2d quasi-random sequence and looked at the x-rank vs. the y-rank you'd get something interesting.
--John
|
|
Top
|
|
|
|
|
#165643 - 16/06/2003 09:01
Re: Strange randomization
[Re: tfabris]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
Ok Tony, here's a new version. It looks sort of like a disk-defragmenter, but I suppose that's going to be best for what you're trying to see. Anyhow, I've color-coded the albums (with up to 6 distinct colors) so you can see artist combs and album combs. To help the eye I wrote an "outline" around combed albums/ artists, which you can switch between the album and artist via a checkbox. I added "find album comb" and "find artist comb" buttons to find the artist/ album with the most combs (a comb defined as a “run of songs separated by no more than 10 other tracks”). The "find artist" button is now automatically called after pushing the "Go" button. I decided not to put a scroll bar in, but you can re-size the blocks to make them all visible with a zoom in and zoom out feature.
Clearly, there is some combing in all random selections. What I'm not sure is if the amount of combing showing up in my program is the same as on the Empeg. It's hard to tell because ultimately we are perceiving this data in a different way than listening through the playlists. But here you have it anyway.
Attachments
164199-RandomNumbers.exe (111 downloads)
Edited by FerretBoy (16/06/2003 09:05)
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165644 - 16/06/2003 10:55
Re: Strange randomization
[Re: JeffS]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
WOW that is so perfect. And yeah, from the looks of the output, it's normal to see clustering.
I will be doing the FAQ entry and linking this file when I get a moment today. Busy day for me...
|
|
Top
|
|
|
|
|
#165645 - 16/06/2003 11:13
Re: Strange randomization
[Re: tfabris]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
WOW that is so perfect. Glad you like it. This is probably the most coding I’ve done in the last two weeks. I actually started feeling productive! I will be doing the FAQ entry and linking this file when I get a moment today. My program in the FAQ? I feel so . . . honored! Truly I'm glad to have finally done something "useful" here, though I have a feeling this won't end all discussions. As I said, it's still hard to tell if the clustering is the same between my program and on the Empeg. I'm just glad I didn't end up proving the Emepg guys wrong, as I began to fear on Friday.
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165646 - 16/06/2003 11:24
Re: Strange randomization
[Re: JeffS]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
What the program shows me is that it's our perceptions that make it seems like we're getting clusters and/or combs of artists. When as few as three songs by the same artist or the same album come close enough together, we start thinking "Jeez, this player is playing nothing but Metallica today!".
But what this graph shows is that it's not only expected, but it's actually common for clusters of artists and even albums to appear. And when you see the boxed clusters on the screen (nicely done, by the way), you can see that it's just a brief concentration that's not much different than the other songs in the shuffle.
The only reason we all keep thinking it's something wrong with the shuffle is because the empeg is the first player we've owned that lets us hear this many different artists in one place. So we just assume that having that many artists means we won't hear the same artist close together. But when you look at the distribution graph, we see it's still inevitable.
Too cool. Great work, thank you SO much!
|
|
Top
|
|
|
|
|
#165647 - 16/06/2003 11:27
Re: Strange randomization
[Re: tfabris]
|
carpal tunnel
Registered: 19/01/2002
Posts: 3582
Loc: Columbus, OH
|
<-- bends over and waits for the obligatory "I told you so" from team empeg
_________________________
~ John
|
|
Top
|
|
|
|
|
#165648 - 16/06/2003 11:32
Re: Strange randomization
[Re: JeffS]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
Quick question... In the program, what's the criteria for it considering something to be a cluster? (And I wonder if the wording in the program should be called "cluster" instead of "comb" but that's not important really.)
It seems to consider any group of songs that is more than two to be a cluster (which is reasonable), but what's the distance-between-songs criteria? It seems like you've chosen a reasonable criteria for this (it seems like I'd perceive the songs to be too close together based on the boxes you've drawn), I'm just wondering what that criteria is.
|
|
Top
|
|
|
|
|
#165649 - 16/06/2003 11:34
Re: Strange randomization
[Re: JBjorgen]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31565
Loc: Seattle, WA
|
bends over and waits for the obligatory "I told you so" from team empeg Yeah, agreed.
Sorry I ever doubted you guys.
|
|
Top
|
|
|
|
|
#165650 - 16/06/2003 11:44
Re: Strange randomization
[Re: tfabris]
|
carpal tunnel
Registered: 14/01/2002
Posts: 2858
Loc: Atlanta, GA
|
And when you see the boxed clusters on the screen (nicely done, by the way), Thanks. As with all good software features, I put this is because I was missing it. I’d already coded the “find the most clustered album” code and realized I was having trouble identifying the clusters. And I wonder if the wording in the program should be called "cluster" instead of "comb" but that's not important really. I can change it to whatever you like. It seems to consider any group of songs that is more than two to be a cluster. Correct. I thought about flagging “two-fers”, but decided against it. What's the distance-between-songs criteria? Ten songs max, though I could make this settable if you wanted. This seemed like a good number because it's shorter than most album lengths, so I'd think it'd really stand out.
_________________________
-Jeff
Rome did not create a great empire by having meetings; they did it by killing all those who opposed them.
|
|
Top
|
|
|
|
|
#165651 - 16/06/2003 12:21
Re: Strange randomization
[Re: JeffS]
|
old hand
Registered: 20/03/2002
Posts: 729
Loc: Palo Alto, CA
|
OK, I don't want to start another tangent on the random fxnality, but...
What I've noticed happening on my empeg in shuffle mode is not so much a clustering of a few songs by the same artist separated by some other songs, but rather a very distinct grouping of songs by artist (or songs just close together in my playlists) back to back. For example:
Random song
Random song
Collective Soul song
Collective Soul song
Dave Matthews song
Dave Matthews song
Random song
Tom Petty song
Tom Petty song
Random song
Random song
Random song
...
This really does happen quite a bit (often enough that I find it hard to be coincidence) and I've talked with other empeg owners on this bbs who have experienced it, too. So, maybe this can still be explained with what you two have been analyzing, but I do find it odd. I really don't mind it, though.
- trs
_________________________
- trs
|
|
Top
|
|
|
|
|
#165652 - 16/06/2003 12:24
Re: Strange randomization
[Re: trs24]
|
carpal tunnel
Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
|
I really wish the empeg fellas would consider opening up just the shuffle algorithm's source code to put this issue to rest. That's obviously not something they can do, but it'd certainly save a lot of discussion on this very tired topic.
|
|
Top
|
|
|
|
|
|
Previous Topic
Index
