Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How random is xkcd? (2015)

hardmath123.github.io

Post reply on HN
Print view View original

71–80 of 133 posts

Re: How random is xkcd? (2015)

#71

Post by Semaphor »

physicles wrote: post #46
Semaphor wrote: post #44

Earlier quoted context omitted.

I once wrote a small script (in C#) to pick a few tens out of a few 1000s. I got weird repeats. I switched to a cryptographically secure RNG, and the repeats were gone. It was probably pure chance, but I stopped using the normal random function ever since ;)

Do you still have your original code? Finding out if the weird repeats were real, and especially why, would make a super interesting blog post.

The old code was var r = new Random() ;)

I'm assuming I either hit an PRNG bug (after all, I encountered a compiler bug in university already), or more likely, that I simply imagined the issue or bad bad luck with the data. Never did a statistical analysis after all.

Re: How random is xkcd? (2015)

#72

Post by observer5 »

defrost wrote: post #2

* Then, I fed them to the NIST Statistical Test Suite. * I encourage you to play with the STS code. * It also segfaults all over the place, which is actually very disturbing considering that it’s technically part of the US government’s computer security project. Well, package that computes stats on number series to test variopus notions of randomness - it's not as if pwning the STS will let you play a game of nuclear…

Segfaults are reported in section 10 of

  https://scholar.google.com/scholar?cluster=189992958054266148
The paper also reports in section 7 the state-of-the-art in statistical tests --- DIEHARD and NIST STS seem obsoleted by TESTU01.

Re: How random is xkcd? (2015)

#73

Post by Semaphor »

GuB-42 wrote: post #70
Semaphor wrote: post #44

Earlier quoted context omitted.

I once wrote a small script (in C#) to pick a few tens out of a few 1000s. I got weird repeats. I switched to a cryptographically secure RNG, and the repeats were gone. It was probably pure chance, but I stopped using the normal random function ever since ;)

Just for curiosity sake, I looked at the standard RNG in C# and it is indeed flawed, but probably not enough to be seen unless you are doing formal tests. In [1] it says that numbers have a 0.5034 probability of being odd due to rounding errors in the algorithm that picks a number in a range, which is unacceptable for a simulation, but may actually be better than a real coin toss [2]. The raw RNG is also flawed but n…

Okay, now you made me want actually look into that ;) I should be able to recreate the old code (it was years ago, but I still have the script) and make a comment if I end up actually finding statistical anomalies.

Re: How random is xkcd? (2015)

#74

Post by bonyt »

I was able to recreate this, eventually. I deleted my earlier comment where I failed to reproduce it - my method of extracting a bitstream from the list of numbers was flawed.

First, I greedily requested 10,000 random numbers from xkcd with a script. These numbers are here so nobody need re-commit my deed: https://gist.github.com/tonyb486/0da38e7575071f241551d14101a...

Then, I filtered out all numbers 2048 and above so that I just had 11 bits of entropy from each number from [0,2048). I converted that to a stream of binary in ASCII, 11 bits per random number.

I fed that list of 78100 bits into STS, as 100 streams of 780 bits. It segfaulted, but it had already written out some results:

   ------------------------------------------------------------------------------
   RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
   ------------------------------------------------------------------------------
      generator is 
   ------------------------------------------------------------------------------
   C1  C2  C3  C4  C5  C6  C7  C8  C9 C10  P-VALUE  PROPORTION  STATISTICAL TEST
   ------------------------------------------------------------------------------
   13  15   7   9   7   6   9  11  17   6  0.137282     97/100     Frequency
   13   5  10  12  11   7   4  10  12  16  0.191687     98/100     BlockFrequency
   13  11  14   9   2   9  10   7  13  12  0.249284     97/100     CumulativeSums
   11  10  12  11   1  10   9  15   8  13  0.181557     98/100     CumulativeSums
   6    6   8  18   9   8  11  14   7  13  0.122325     99/100     Runs
   16   7   6  12  13   9   7  14   9   7  0.275709     97/100     LongestRun
   10  13  12   0  23   0  18   0  24   0  0.000000 *   99/100     FFT
Delightful.

Re: How random is xkcd? (2015)

#75

Post by 2143 »

BillyTheMage wrote: post #45
avianlyric wrote: post #30

Earlier quoted context omitted.

There’s a really good article from Spotify Engineering that looks at exactly how Spotify bridged this gap between “random” and the “random” people actually expect. https://engineering.atspotify.com/2014/02/how-to-shuffle-son... It a good read on understanding what people generally expect when they ask for a random stream of songs (or comics), and how you can meet that expectation by carefully engineering how you gene…

Anecdotally, Spotify shuffle is one of the worst shuffles I've ever used. Or at least it used to be, not sure about now since they added Smart Shuffle. At least used to, maybe still, it would play a lot of songs over and over, but never play others. Like it had maybe 100 songs out of 2000 playing regularly, over and over. This isn't just me, but all my friends too. We're all the time finding old songs we saved that h…

> Me and my friends tend toward 1000+ songs in a playlist, but most other playlists I've found are rarely over 250 songs.

Oh it's bad with small playlists as well.

This problem exists even with a smaller playlist. My playlists have about 150 songs each. And every time it plays a certain subset of songs a lot more frequently than others.

Re: How random is xkcd? (2015)

#76

Post by suzzer99 »

kemayo wrote: post #64
stronglikedan wrote: post #48

Earlier quoted context omitted.

Their shuffle is completely broken, but so are all modern streaming music players. It used to be that shuffle would do just that - shuffle the deck of cards (playlist), and then deal the cards in order, never repeating until all cards have been dealt. Now it just keeps the playlist in the same order it was in and jumps all over the place, repeating songs and never playing some. It's very frustrating and woefully brok…

For what it's worth, in the streaming music players category, Apple Music does shuffle as you want it. Probably because it is an old(er) media player, just with a streaming service bolted on. (i.e. if you tell it to shuffle, it'll take the playlist, put it in a random order in your queue, then play through every song once.)

iPod Shuffle is the same.

Re: How random is xkcd? (2015)

#77

Post by KMag »

ahoka wrote: post #33
hbn wrote: post #31

I remember hearing Apple had to make a "random-seeming to humans" algorithm with the iPod's shuffle feature as well for the same reason. Grabbing a truly random song every play doesn't feel random to humans. What people really want with their song shuffle is something new they haven't played in a while.

Random is random, shuffle is shuffle. They are different things.

And a uniform random shuffle chooses any of the N! orderings with equal probability. One is looking at a single element as the output of the process, and another is looking at the entire list as the output of the process.

Also, there are plenty of non-uniform random distributions.

Re: How random is xkcd? (2015)

#78

Post by bumby »

avianlyric wrote: post #30
mattnewton wrote: post #3

Kind of an aside to the nerd sniping happening here, but I think the fact that people complain about the random button is a sign that the feature isn’t doing what those people really want, even if it is doing what is advertised. Those people _want_ a button biased to return novel ones they haven’t read either in that session or across all time somehow, likely because they are using it to discover new comics.

There’s a really good article from Spotify Engineering that looks at exactly how Spotify bridged this gap between “random” and the “random” people actually expect. https://engineering.atspotify.com/2014/02/how-to-shuffle-son... It a good read on understanding what people generally expect when they ask for a random stream of songs (or comics), and how you can meet that expectation by carefully engineering how you gene…

I believe this issue is pre-dated even further, back when iPod users didn't like that occasionally a random shuffle would play the same song back-to-back. So the 'random' shuffle was made a bit less random.

Re: How random is xkcd? (2015)

#79

Post by roywiggins »

dessimus wrote: post #35
Cyphase wrote: post #9

Using the formula in the article: - Out of 1500 comics (at the time of the article), 45 random selections gives you a 48.656% chance of a duplicate, and 46 gives you a 50.196% chance. - Out of 2873 comics (as of right now), 63 random selections gives you a 49.579% chance of a duplicate, and 64 gives you a 50.685% chance. 2929 comics is the most from which randomly selecting 64 will have a greater than 50% chance of h…

Seems like a variation on the birthday paradox.

The difficulty of finding unseen comics as you keep pressing "random" is more like the coupon collector's problem, but of course they're related.

https://en.wikipedia.org/wiki/Coupon_collector%27s_problem?w...

Re: How random is xkcd? (2015)

#80

Post by saalweachter »

bumby wrote: post #78
avianlyric wrote: post #30

Earlier quoted context omitted.

There’s a really good article from Spotify Engineering that looks at exactly how Spotify bridged this gap between “random” and the “random” people actually expect. https://engineering.atspotify.com/2014/02/how-to-shuffle-son... It a good read on understanding what people generally expect when they ask for a random stream of songs (or comics), and how you can meet that expectation by carefully engineering how you gene…

I believe this issue is pre-dated even further, back when iPod users didn't like that occasionally a random shuffle would play the same song back-to-back. So the 'random' shuffle was made a bit less random.

CD players inspired the same discussion.

Probably doesn't go back further than that, unless jukeboxes has a random play option.

Post reply on HN