11 ms·

How random is xkcd? (2015)

• defrost 3y ago
  * 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 war. All the same, there's an exercise for any budding numerical programmers, read up on the suite, build it, run it, static analyse it, valgrind it, and iron a few wrinkles out. https://csrc.nist.gov/projects/random-bit-generation/documentation-and-software https://csrc.nist.gov/projects/random-bit-generation/documen... Got to be worth a humble brag in an application or two | make contacts in NIST.
  • observer5 3y ago
    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.
• mattnewton 3y ago
  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.
  • mjburgess 3y ago
    The term `random` is a relative one, X is random wrt to Y, iff P(X|Y) = P(X) Random data is highly patterned regardless. The choice of Y=everything-but-/dev/random is has no special status (ie., P(X|/dev/random) = 1). Better than `random` is set to draw from the long tail of lower-rank-by-view comics. Then Y = the-url / user-preference / ...
  • aebtebeten 3y ago
    If XKCD would not be able to have a feature which is technically but not socially correct, then what webcomic may? The people who learn that random(uncorrelated) is what it is and not what they want are part of today's lucky 10'000
    • nevinera 3y ago
      Indeed, if I were running that site, I would now implement the ability to turn on intentional non-randomness for _specific people_, and begin embedding messages in the sequences of comics, or selecting the same two comics 28 times in a row on occasion. Heck, stick the referrer in the session and give everyone coming in from _that blog post_ wildly divergent randomness characteristics :-)
  • madeofpalk 3y ago
    Plainly, it’s the difference between picking one at random, or shuffling a playlist. I think people can intuitively understand the difference between the two.
    • saghm 3y ago
      Yeah, I think the word "shuffle" itself indicates what people are actually looking for here; when I shuffle a deck of playing cards, I'm changing the order, but I'm still getting every card exactly once when I deal them. Nobody claims that the deck order isn't random because you can't get the 7 of clubs twice after shuffling it.
  • madaxe_again 3y ago
    Correct conclusion IMO. Many years ago I ran a social network with a focus on art and media, and we had a “show me another” button which picked a random submission to display. People complained that it wasn’t random. Incessantly. So I changed it, to instead maintain a list of previously viewed items for each user, and to exclude them from the results. And that was that. People almost immediately noticed that it had been “fixed”. There’s mathematically perfect, and then there’s user expectations - and ne’er the twain shall meet.
    • dspillett 3y ago
      > instead maintain a list of previously viewed items for each user, and to exclude them from the results For something like XKCD this is a very good idea. It mitigates two possible perception problems amongst users: 1. Regular long-term readers who see true random as less so because it seems to show them things they already remember more than novel examples. 2. People who are regular and been around a while, but not for the half the length of the site's long history, because again they'll see less of what they've already seen than they would with true random. The issue for a site like XKCD is the fact that many won't want to be tracked so for them any such effort is wasted. You can store the data in localstorage (it is a feature that can live without needing to track the same user between different devices and UAs) to mitigate the concern, but that is usually blocked by blocking cookies due to it having similar potential for more nefarious activity tracking. To be honest, I'd just not bother. People will still complain anyway!
  • nullhole 3y ago
    Sid Meier talked about this wrt Civilization battle odds: https://youtu.be/bY7aRJE-oOY?t=1101 https://youtu.be/bY7aRJE-oOY?t=1101
    • ketzo 3y ago
      Oh man this is an awesome talk, thanks for linking! Quick excerpt: > The player said “I lost a 2:1 battle, and I get that, I know I should lose that sometimes.” > I said, okay, so what’s the problem? > He said “well, I lost a 20:10 battle — what’s up with that?! 20 is so much more than 10!”
      • igiveup 3y ago
        Is that wrong? I don't know the logic of the game, but a 20:10 battle can very well have different odds than a 2:1 one.
        • kemayo 3y ago
          They're talking about ratios of unit-strength, which correlate directly to odds of success in a battle, not to numbers-of-units or anything more fuzzy like that. Given which, 20:10 and 2:1 have identical odds of success.
          • waterhouse 3y ago
            Do they, though? It depends on how the combat works. Suppose, for example, that each side has 5 hit points, and repeatedly you roll a 2:1 die to decide who gets 1 point of damage, until one side reaches 0 hit points. The chance of an "upset", where the weaker side wins, is not 1/3; I compute it to be roughly 14%. If both sides start with 10 hit points, I compute the chance of an upset to be 6.5%. The law of large numbers means that, the more die rolls the combat involves, the less likely an upset is. Or. Suppose that, at each step, one side has N soldiers and the other has M, and repeatedly a random soldier gets a kill; so that's an N/(M+N) chance that the first side gets a kill, and M/(M+N) that it's the other side. This would make advantages compound within the battle. Then I compute that a 2:1 initial matchup has a 5/6 chance (83%) of victory, and a 10:5 matchup has a 98.8% chance of victory. (edit) I guess you could say I'm challenging the idea that "unit strength", such that when strength A fights strength B it's decided in one step with probability A/(A+B), makes sense as an abstract concept. (defmemo meh (a b p) (if (is b 0) 1 (is a 0) 0 (+ (* p (meh a dec.b p)) (* (- 1 p) (meh dec.a b p))))) (defmemo nub (a b) (if (is b 0) 1 (is a 0) 0 (+ (* (/ a (+ a b)) (nub a dec.b)) (* (/ b (+ a b)) (nub dec.a b)))))
  • deleted 3y ago
    [deleted]
  • avianlyric 3y ago
    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-songs/ 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 generate “random” lists.
    • BillyTheMage 3y ago
      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 have never once been played with shuffle, while it's played this one song 3 times in the same day. Perhaps it doesn't work as well with large playlists? Me and my friends tend toward 1000+ songs in a playlist, but most other playlists I've found are rarely over 250 songs.
      • stronglikedan 3y ago
        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 broken. Old media players did it correctly.
        • dwringer 3y ago
          Agreed; the suggestion that people just expect random shuffle to work differently from that seems well-meaning and rooted in some kind of truth but quite disconnected from the fact you stated. I'm not sure why media players that offer something other than a true "shuffle" can't just provide the option to have either functionality.
  • t_mann 3y ago
    The button may be 'correct' in its randomness under one meaningful definition of the word (draw the next element uniformly at random from the whole set on each click), but that's not the only plausible definition of randomness here. Another perfectly reasonable definition would be 'cycle through all elements in random order', ie similar to the randomness in a shuffled deck of cards (which is a reasonable analogy for a series of cartoon clips, and perfectly doable even without cookies, at least within the same session). So in this case, you wouldn't even have to sacrifice formal correctness to please your users, you'd just have to pick the right formal model that corresponds to the kind of randomness you want here.
  • kelthan 3y ago
    First off, let me give a shout out to the author of the article. It's quite well written with clear support for the answer he provides. Now back to the thread: It turns out that most people expect "random" to mean a random selection without duplication (at least until the source is exhausted). That is called a non-replacement randomization: once a song (or comic, or whatever), is played/displayed, that item is no longer considered as part of the pool for future selection. However, that requires saving state for the individual user to save which information has been presented to this specific user, which adds a whole lot of additional requirements for cookies, or account registration, or other things that we all generally loathe. The fundamental problem here is that most people don't really understand randomness and probability. If they did, casinos and lotteries would be out of business (see The Gambler's Fallacy[1]). This is not a failure of education, or mental capabilities: it is a fundamental friction with the way that the human brain has evolved. The human brain is fundamentally a pattern matching system. We look for "meaning" by identifying patterns in our world and extrapolating what actions we should take based on those patterns. As such, we assume that _all_ systems have memory because that's how humans learn and take action, so we generally assume everything else does, too. But truly random events have no memory: there are streaks that appear "non-random" to us, such as multiple tails occurring in a streak during a fair-coin flip. But streaks often occur in truly random data, we as humans just don't expect it. The existence of the Feynman Point[2] is an example that even someone well versed in randomness and math thought that a string of six 9's appearing in the value of PI, an irrational number, was something worth noting. [1]: https://www.investopedia.com/terms/g/gamblersfallacy.asp https://www.investopedia.com/terms/g/gamblersfallacy.asp [2]: https://en.wikipedia.org/wiki/Six_nines_in_pi https://en.wikipedia.org/wiki/Six_nines_in_pi
    • thrwggrdxvgf 3y ago
      > If they did, casinos and lotteries would be out of business I think you misunderstand the reason many people gamble if you are so sure of this. (But I agree people also don’t really “get” randomness).
  • bmeow_engineer 3y ago
    This happens a lot in game development too. Many games have "random" elements that end up with lots of duplicates as the developer uses a typical random number generator. I've found in games I worked on to make it "feel" random you have to tweak the algorithm to reduce duplicates and make things more evenly distributed.
• flir 3y ago
  > a random stream of bits should have almost as many ones as zeros almost??
  • xvedejas 3y ago
    I think this is the correct way to phrase it. Just because the probabilities of each are both 50% doesn't mean it's more likely than not to get the same number of ones and zeros. It would just mean you're equally likely to get a few more ones as you are to get a few more zeros. But the counts are unlikely to be very far apart.
    • 082349872349872 3y ago
      But in absolute (not relative terms) the counts will tend to diverge over time.
      • eru 3y ago
        Yes. You expect the absolute difference in numbers of 0s vs 1s to grow roughly with the square-root of the total number of digits produced.
  • philipswood 3y ago
    In the limit, yes. But for the first few bits maybe "almost".
  • thisisauserid 3y ago
    You aren't suggesting that something random should be predictable, right?
    • 0xFF0123 3y ago
      "Almost" suggests it is predictably fewer
      • AlecSchueler 3y ago
• Cyphase 3y ago
  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 having duplicates (50.00854657587404%).
  • dessimus 3y ago
    Seems like a variation on the birthday paradox.
    • roywiggins 3y ago
      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?wprov=sfla1 https://en.wikipedia.org/wiki/Coupon_collector%27s_problem?w...
• jalada 3y ago
  Reminds me of Spotify's post about shuffling songs: https://engineering.atspotify.com/2014/02/how-to-shuffle-songs/ https://engineering.atspotify.com/2014/02/how-to-shuffle-son...
  • GuB-42 3y ago
    I actually how people do purposefully non-random randomness more interesting. Like in this article. Video games are known to cheat a lot, usually in the player's favor. The Tetris randomizer for instance is well documented. Early games drew pieces truly randomly, but now, the standard is to draw randomly from a bag of all 7 pieces until it is empty, then repeat, limiting flood and draught. Along the way, other algorithms have been used with the same purpose. But sometimes, even the numbers are fake, for example, a 95% success rate may be closer to 99% in reality because it matches more closely what players feel 95% should be like.
    • Semaphor 3y ago
      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 ;)
      • physicles 3y ago
        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.
        • Semaphor 3y ago
          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.
      • 3y ago
• i_love_limes 3y ago
  I ran into this too. I run a very silly slack bot for my friends, and it randomly cycles through pictures that we all have created. Initially it was completely random choice per invocation. Had to change it to a randomly sorted list that was then stored and iterated through until the list is depleted, then it's re-randomised. For the same reason, complaints that actual random choice chose duplicate pictures too often
  • KMag 3y ago
    Note that if your playlist is append-only, you can use format-preserving encryption and just store a seed, a counter, and the length of the list when you started, instead of storing the whole shuffled list.
• mysterydip 3y ago
  Sometimes the random button should just return 4 multiple times in a row, as a reference to https://xkcd.com/221/ https://xkcd.com/221/
• hbn 3y ago
  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.
  • littlethoughts 3y ago
    > What people really want with their song shuffle is something new they haven't played in a while. Speak for yourself
    • moffkalast 3y ago
      I mean I'd agree with OP, shuffle should take all songs, put them in random order and play them start to finish without any of them repeating. If I wanted repeat then I'd turn on repeat.
  • ahoka 3y ago
    Random is random, shuffle is shuffle. They are different things.
    • uxp8u61q 3y ago
      "Random" doesn't necessarily mean "uniformly distributed random." Shuffling a deck of cards randomly is random, but you're not going to get the same card twice in a row, or even the same card twice until you go through the whole deck.
      • Karellen 3y ago
        Do you re-shuffle after the deck is exhausted, or after every hand? It's not excessively unusual to be dealt the same card twice in two consecutive hands.
        • uxp8u61q 3y ago
• DarkmSparks 3y ago
  Hmmm, I might check how often an m twister gives duplicates. that was always my complaint with xkcds random, getting the same couple of pages repetitively.
• jmclnx 3y ago
  For laughs a while ago, I wrote a program to read /dev/urandom and print integers. It can execute between a range and let it print out 200,000 iterations. This is some highlights from executing it using 1 -- 2873 using `sort | uniq -c`: 2873 unique numbers printed, so I got all of them for xkcd as of Dec 28, 2023. The lowest occurrence of a number 44 unique entries for 332 and 1829. The largest occurrence of a number was 99 unique entries for 2007 and 2230. Average occurrence was 69 entries, 134 unique numbers occurred 69 times. What does this mean to me ? Nothing, but maybe to a mathematician it will mean something :)
• zepton 3y ago
  There actually is a bias - you will never get comic 404 from the random button (see https://www.explainxkcd.com/wiki/index.php/404:_Not_Found https://www.explainxkcd.com/wiki/index.php/404:_Not_Found )
• deleted 3y ago
  [deleted]
• amelius 3y ago
  The real question is how uniform the randomness is.
• seqizz 3y ago
  Related: https://www.tomasek.cz/software/debian-randomness/img/pmeo9hcjp7aw9.jpg https://www.tomasek.cz/software/debian-randomness/img/pmeo9h...
• bonyt 3y ago
  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/0da38e7575071f241551d14101a3886e 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 <xkcd.ascii> ------------------------------------------------------------------------------ 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.
• wkjagt 3y ago
  Maybe they use their own random number generator. https://xkcd.com/221/ https://xkcd.com/221/
• seanhunter 3y ago
  Feels like there are two things going on: 1. Randomness is inherently counterintuitive and humans in general really struggle to comprehend its ramifications. Read “Fooled by Randomness” or a million other things about this. 2. When a lot of people see something which offers a random sample they expect a random shuffle. In particular if you’re making any kind of playlist thing and you have a feature which does random samples not random shuffles people will hate your feature and you’ll feel superior because you’ll think they are wrong but actually you are the one who is wrong. You need to build a shuffle of some kind. Changing your sampling strategy to be “less random” thinking that it will coincide with peoples’ intuitions is making it even more wrong than before.
• MikeBattaglia 3y ago
  XKCD should solve the problem the same way Tetris randomizers do. In Tetris, they don't use naive memoryless uniform randomizers for pretty much the same reasons that people are complaining about in this article: you tend to get these long droughts and floods of pieces that you want or don't want. Instead, they just do a random permutation of all 7 pieces, spawn those, then do another random permutation, etc. XKCD could easily do this kind of thing (with cookies, I guess).