How random is xkcd? (2015) | Hacker News Reader

How random is xkcd? (2015)

hardmath123.github.io

209 pointsscreeny05128 comments

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 generate “random” lists.

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.

Just from reading the article you can see how bad it is, and it makes sense that it would be worse for larger playlists. They've completely discounted the fact that when you play large playlists, you don't listen to the whole thing. The problem with the dithering comparison is that in dithering, you're looking at the whole image at the same time. But nobody listens to a long playlist all at once.

First of all, the core idea that Same Artist == Similar Song and Different Artist == Dissimilar Song is already flawed. There are just way, way more axes than that. Getting 4 slow songs in a row in a playlist of mixed slow & fast dance music is going to feel very bad for everyone.

They give each artist one single "random offset". If this is uniform over [start, end], then it would absolutely kill artists that show up a lot on your playlist, dramatically in favor of artists you have once or twice. If it's from [start, end/N] with N being the number of songs of that artist, it would be a little better, but it's still making the playlist behavior completely different at the start (where it's mostly completely random) from the middle/end (where it's "dithered"). If it's [start, end/M] with M being anything else, it's again dramatically favoring the artists with fewer songs on the playlist.

Instead, they could introduce a "ghost" song for each artist that gets shuffled in and then discarded (or possibly some small constant number of ghosts).

I think you're onto something here. Spotify already saves various metadata about the musical qualities of songs like how "upbeat" it is or how much it "slaps". I'm imagining some kind of K-farthest-neighbors algorithm could make it so that you're constantly being given songs that are as different as possible from the recent ones you've listened to. I dunno, I'm not very well versed in algorithms yet, maybe that would be way too slow.

In the early 1980s I worked in the incoming stock dept of the worlds largest record store (we were physically separated from the actual store). We had an employee controlled music system, mostly playing mix tapes. One of the goals of many of us was to create a never-ending stream of "constantly being given songs that are as different as possible from the recent ones you've listened to"

We were young and not that well versed in the full range of musical expression (yet). Nevertheless, that didn't stop one of us (me? not sure) hitting it out of the park with a 3 part segue from "King of the Swingers" from The Jungle Book soundtrack to the Sex Pistols "Pretty Vacant" to one of the Bach preludes from the WTC. This sort of thing was routine on a daily basis for all of us, and we delighted in the best ones.

I don't even understand the goal here. My playlists are built up around topics and themes - most songs in playlists I build are going to be not very different.

I think there's probably a different optimum shuffle experience for real playlists like you describe vs. "all my liked songs" where the latter is often what I'd put on in the car by default.

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.

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.

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.

Well, as long as you don't go too far back: Old hardware media players with shuffle (mp3 players, even my cd player had a shuffle button) often used the same random seed, resulting in the same random order. My guess would be by accident due to restarts not preserving information.

Yeah, Spotify's shuffle sucks. I have the same experience with it picking "favorite" songs and choosing to replay them many times while others in the list go unplayed forever. Maybe it believes those songs are my favorites because of how many times they've been played, in a form of circular reasoning.

I think I would be happy with a weighted random selection. Take 2 (or K) random numbers in range [0.0,1.0] and multiply them together to get X. X will favor the low end of the [0.0,1.0] range. Now sort the playlist from least recently played to most recently played. Next song = playlist[round(X * (playlist.Length - 1))].

Something like that. Note that "least recently played" would be a persisted attribute, not something that gets discarded in each shuffle "session". And not even local to this playlist -- just literally what is the last DateTime at which I played that song from my Spotify. It's possible to get a repeat but rare. When I hear a song I enjoy I know I could hear it again soon -- I'm not going to have to work through my entire library to hear it again -- but the odds favor hearing older stuff.

You could also remove the last N songs from the candidate list completely if you wanted to guarantee never repeating super recent tracks. Increasing the K factor would increase the favoritism of long-unplayed songs.

> 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.

I think you're right. Recently I spent a bit of time writing about and playing with various shuffling algorithms, trying to see if I could find something that works better for me than the built-in shuffle.

The answer is: it's hard! An algorithm that works for a well-distributed set won't work so well for something with large clusters of similar stuff (think a mixtape vs a playlist consisted of a dozen albums from six different artists). And even when you think you've come up with a good solution, it works well six times, and then the seventh you start to find something that doesn't work quite how you like. It's a process of tweaking.

My final test case was a large playlist like you describe, since I have a few of these, too.

This is what I found worked best for me:

- (Optionally) Fisher-Yates shuffle the whole thing, then - Slice the playlist into X chunks - Shuffle the order of the chunks using Fisher-Yates - Analyze the contents of the chunks - Pick a suitable shuffling algorithm based on the contents - Shuffle the contents of each chunk

There are lots of details around things like, how recently was this artist/album/compilation played? What's the relative tempo or genre of the most recent X songs, and how "harshly" are we willing to change it up? Is this a playlist with a lot of disparate songs (by artist/album/compilation) or is it a collection of like-minded albums and artists? Is the playlist just someone's discography? etc.

It takes a lot of passes and a lot of listening to find and tweak these things to find something that works and feels good. And in the end, I don't think the people who can do this are incentivized to actually do this. Especially considering the linked Spotify article is an entire decade old by now, and the Every Noise at Once guy was let go seemingly at random by Spotify. They care about "good enough for now" more than Actual Quality.

That seems like the real problem with Spotify shuffle. The thing that feels un-random about it is that it plays the exact same songs over and over again despite the humongous size of the playlist. It's not that it plays the same artist, or that every once in a while you get a repeat song. Once you get one repeat they're all repeats.

I wish it would randomly pick the next song from the entire playlist whenever it changed songs.

Though as you say it might already be doing this now. I don't remember feeling like I'm rotating through the same 30 or so songs recently. But also I did start working around it, so I may just not be noticing.

> 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.

That isn't "shuffle", that's "random".[1]

Normal people know what "shuffle" means. It's only recently (since the iPod?) that tech companies tried to blame the user when the user hit the "shuffle" button and got "random" instead.

[1] When you shuffle a deck of cards and then look at each one in turn, do you expect to see a King of Hearts three times in a row? Why on earth, then, is it acceptable to blame the user when they shuffle a list of songs and then get some songs player twice and some not at all.

I've noticed this too! It's especially bad after using discover weekly and liking a song or two, the shuffle then gets stuck on similar songs. It seems disabling "automix" in the settings returns the shuffle to be more like a traditional random shuffle.

yep spotify has always had this issue which is why it blows my mind that anybody uses it at all. it just takes a very small handful of the songs in a playlist and then shuffles those endlessly, which makes the entire service useless as far as i'm concerned. it's actually just kind of sad, it just isn't a difficult problem to solve, i'm 100% certain one of their junior devs could fix it in an afternoon.

i switched to apple music because of this, which does work properly (unless youre using the web client, in which case you can't click the shuffle button because it only queues up the songs from the first lazy-loaded "page", so you have to scroll all the way to the bottom, play a song from the last "page", then put it into shuffle mode)

youtube music is probably the best option for music streaming if you can stand to give them your money.

> 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.

This is precisely why I stopped using Spotify. The random was also horrible as you start to "like" songs, those songs continue to show up during random which isn't random at all. Of all of the vast number of songs Spotify claims WTF am I hearing the same ones over and over. If I wanted that, I'd tune into the radio!

I suspect it has something to do with how Spotify makes money and the likelihood they would intentionally bias their service towards playing songs that generate higher revenue per listen. If the complaints are not an example of the bias the article talks about, that is.

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.

I think the issue was playing the same artist or album back-to-back. So they made ‘smart shuffle’ in 2005. (https://www.wired.com/story/requiem-for-the-ipod-shuffle/)

A shuffle already implies shuffling like a deck of cards, so you wouldn’t get duplicates unless you had two of the same card, and I that’s how it was described in the manual.

Is there any algorithm that would do that without actually storing a list of indices, or track IDs?

I can't think of why someone would prefer a truly random song being played from a playlist rather than the "deck of cards" method.

CD players inspired the same discussion.

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

You don't need to make it less random to achieve that. A 100% random shuffle won't have that issue, you just have to make sure it's actually a shuffle and not something else.

Given a set of songs or albums {a, b, c}

Suppose shuffling results in ordered set [b, a, c]

Suppose user plays through the entire set. Now it's shuffled again before repating.

Suppose the new shuffle results in ordered set [c, a, b]

The user now hears c play after c

I'm going to ignore the other ways to handle that and just point out that that is multiple shuffles and won't be a problem if the user initiates all shuffles.

If the user has to initiate all shuffles, it won't play continuously. If you handle it another way, that demonstrates that it doesn't "just" work with a pure shuffle without using those tricks.

1. Without a clearer spec, we should not assume the user wants any repeats at all.

2. Your claim is not even true as written.

3. I'm tempted to assume the user has a reasonable amount of music, so it will last as long as necessary. And you can't force me not to assume that.

It can be biased and still random.

Can you explain that?

A non-uniform probability distribution is still a probability distribution, and, as long as it doesn’t assign probability 1 to any particular outcome, is still “random”.

There was a dark time with Spotify where ‘random’ played me a couple of random tracks then Cyndi Lauper. Glad that came right.

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.

> 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!

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.

Sid Meier talked about this wrt Civilization battle odds:

https://youtu.be/bY7aRJE-oOY?t=1101

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!”

It seems reasonable to assume that's it's instead something like 10 simultaneous 2:1 battles, and you need to win a majority of them. That's very different odds than a single 2:1 battle.

He seems stuck on interpreting feedback through the lens of a linear-odds, one-shot model. The player feedback is that it shouldn't be linear, and there should be less randomness for larger numbers.

That all makes sense to me... and I suspect makes sense to him when he's not giving a talk for comedic effect.

What do you do when it's 15:7?

Then you probably want to calculate the attacks between two big blobs of units without separating them. But the result is still going to be "something like 7 simultaneous 2:1 battles", and not at all like 30% odds of upset.

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.

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.

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)))))

Sure, you could design a system where it's more complicated, but Sid Meier didn't. In the video he's talking about Civilization Revolutions, in which combat is just "attacker's Attack stat vs defender's Defense stat" to form a probability-of-success, which is then rolled to see who won the battle. There's no hit points or anything like that, just those stats.

More than "players don't understand math", this might be a UI or tutorialization issue. I.e. presumably it was unintuitive because people imagined more complicated ways it might be working behind the scenes, causing large absolute stat-disparities to feel like they should work differently despite being in similar ratios. It's a case where showing an explicit odds-of-success display might have helped, though XCom famously showed how that can backfire...

(Revolutions was a deliberate simplification of the Civ formula, so they could try to appeal to console / mobile gamers rather than the traditional hardcore PC audience.)

> presumably it was unintuitive because people imagined more complicated ways it might be working behind the scenes

I think this is exactly it. And then Sid Meyer calls his players stupid and irrational for assuming the game had more depth than it actually had. For assuming a celebrated game designer would put even a modicum of thought into making a combat system that was balanced, made sense, and felt good.

It's like selling a gallium spoon and then calling people stupid when it melted in their soups. Sure, if you know a lot about gallium, you wouldn't be so stupid and irrational as to put it in your hot soup. But it's a metal spoon that you bought from a reputable vendor. Spoons go in soup. They were being completely rational; it's just that they were tricked into assuming a product was less crappy than it actually was.

> I think this is exactly it. And then Sid Meyer calls his players stupid and irrational

I think this is overstating what Sid Meier says in the talk. His original goal was to make his simple combat stat system clear to users by describing its odds as odds conventionally are described.

> For assuming a celebrated game designer would put even a modicum of thought into making a combat system that was balanced, made sense, and felt good.

That's exactly what he did, through player testing! Through practice and player feedback seems to me like a perfectly reasonable way to uncover an intuitive notion of unit strength. It's not like he said 'they're odds, stupid! learn how to understand odds.'. He recognized that player intuition and fun was the real goal, and his team gradually made the combat system more sophisticated.

> His original goal was to make his simple combat stat system clear to users by describing its odds as odds conventionally are described.

Except that odds values don't add on to each other. It sounds like the numbers only worked like odds in a single way, and not in other ways. The system was inherently contradictory, and confusion is not irrational in that situation.

And it's easy to clarify something as odds by making it two opposing percentages out of 100.

1:3 (one to three) odds aren't the same as 1/3 odds (1 in 3 odds).

1:3 means the second outcome (that on the right-hand side of the ':' symbol) is 3 times as likely as the former outcome, which is true when the likelihood of the first outcome is 25% and the likelihood of the second outcome is 75%.

1/3 describes the chances only of one of the outcomes, and fixes it at 33⅓%. If there's only one other outcome, its likelihood is 66⅔%.

Is the 'addition' you're talking about just one of the readings of the first syntax, or did I miss something else in the video that made the initial presentation of those odds figures surprising?

Sorry if my terminology is off; it's been a long time since I did any stats

"Player psychology has absolutely nothing to do with rational thought ... the attacking unit has a strength of 1.5, and the defending unit has a strength of 0.5. So the attacking unit should win 3 times for every 1 time the defending unit wins. It's 3:1. That's just math. That's what the math says."

Wow, I liked Sid Meyer a lot more before I listened to that arrogant diatribe about how stupid his players are and about how his decisions are unarguable Math-God-Given conclusions that you'd have to be A Stupid Irrational Loser to disagree with. Fuck you, Sid. You can design your game any way you want. Don't blame shitty game design on math; math didn't make you decide that combat strength should map linearly to odds of winning. That's a shit-ass combat system and not any more mathematically pure than "biggest number always wins", or using a health system like later games did. The audacity to stand up in front of people and lament how he had to get his pure, beautiful game all dirty because of the irrationality of his stupid loser players who just want a game that doesn't feel like bullshit ... come on. So much respect was just lost for that man. Never meet your heroes, nor listen to them talk about how much smarter they are than everyone else.

Hey friend. He's not saying they're stupid. He's saying they're irrational. And he's right. Humans aren't rational beings and our expectations differ from simple mathematical probabilities. When making Civilization 3 in the years leading up to 2001, his team had to make changes to the game so that it felt better to the players. They improved game design as you say that they should have, but made it an internal change so that the presented numbers "felt" right. They learned from this experience and he's presenting this learning in a lighthearted presentation to an audience containing some of the very players he's talking about. They got the humor in the situation fifteen years ago and thanks to that, you, me, and other people making and playing games today expect better presentation in our games.

> He's not saying they're stupid. He's saying they're irrational. And he's right. Humans aren't rational beings and our expectations differ from simple mathematical probabilities.

He's right in that players are biased when it comes to rare player success versus rare player failure. He's not right that it's irrational to have different expectations from the "simple mathematical probabilities".

The simple math works when each side is trying to hit a single target that only needs to be hit once. It does not work for medium or large fights.

> He's saying they're irrational. And he's right.

No, he's not right. Humans only seem irrational when you myopically narrow your focus to one or two axes. This is something "smart" people do all the time: they're smart in one way, so everyone who acts in any way counter to what looks optimal from that narrow, simplified model is acting "irrationally". Economists will call humans irrational, but it's actually their over-simplified models that suck. Sid Meyer will call his players irrational, but it's actually his (originally) lame combat system that sucks. Rich MBAs will call lifelong employees irrational for not starting their own businesses, but they're ignoring a thousand factors that they took for granted. The people they are denigrating are incorporating more axes, more information, more context than their silly little models are.

There's a story I wish I could find about a young boy in India trying to answer his dad's math problems. His dad asks him questions like "A man wants 5 mangoes from a shopkeeper who is selling them for $4 each. How much money will he spend?" and gets increasingly exasperated that his child can't answer. But we see the child's inner thoughts, with things like "why would he spend $4 at this shopkeeper when they usually cost $2? Can't he just walk to a different shop and get them there? And what is he going to do with FIVE mangoes? He won't be able to use them all before they spoil!" etc. etc. Sid Meyer is the dad assuming his players are stupid (sorry, "irrational", meaning: stupid, losers, dumb, idiots, morons). They're not.

You might enjoy Gigerenzer's "Bias bias" paper. Discussed here: https://statmodeling.stat.columbia.edu/2019/07/14/gigerenzer...

Paper itself: https://www.nowpublishers.com/article/OpenAccessDownload/RBE...

Abstract: "Behavioral economics began with the intention of eliminating the psychological blind spot in rational choice theory and ended up portraying psychology as the study of irrationality. In its portrayal, people have systematic cognitive biases that are not only as persistent as visual illusions but also costly in real life—meaning that governmental paternalism is called upon to steer people with the help of “nudges.” These biases have since attained the status of truisms. In contrast, I show that such a view of human nature is tainted by a “bias bias,” the tendency to spot biases even when there are none. This may occur by failing to notice when small sample statistics differ from large sample statistics, mistaking people’s random error for systematic error, or confusing intelligent inferences with logical errors. Unknown to most economists, much of psychological research reveals a different portrayal, where people appear to have largely fine-tuned intuitions about chance, frequency, and framing. A systematic review of the literature shows little evidence that the alleged biases are potentially costly in terms of less health, wealth, or happiness. Getting rid of the bias bias is a precondition for psychology to play a positive role in economics."

Thanks, that paper is arguing something very different from what I'm used to seeing so that alone makes it worth a look. It's nice to see that not everyone is taking it as a given that humans are irrational.

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.

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.

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 [2]: https://en.wikipedia.org/wiki/Six_nines_in_pi

> 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).

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

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 :-)

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.

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 / ...

* 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/documen...

Got to be worth a humble brag in an application or two | make contacts in NIST.

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.

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.

I don't have many memories of experiencing this with my own iPod, but I recently came across this paper - "Does Your iPod Really Play Favorites?" (https://www.researchgate.net/profile/Jessica-Culhane/publica...).

In the paper, the authors examined evidence of nonrandom behavior and created several probability models for these events under the assumption of a random shuffle. Their conclusion was:

> Much of the evidence of nonrandom behavior reported by Steven Levy and others does not hold up when the probability models of the events are determined. Our results show the probability models for a random shuffle in many cases do not match the intuition of users. In addition, our statistical tests show the long-term occurrences of these events are within expectations under the assumption of a random shuffle.

I'm not sure if this was something Apple implemented after 2009.

I think it's gone now, but older versions of iTunes had a "randomness" slider that ranged from truly random to a biased randomness that "felt" more random by avoiding recently chosen songs/albums

I remember this, and I also remember reading anecdotes online about people listening on shuffle, hearing two songs from the same artist or album in a row, and getting superstitious about it like it was trying to "warn them" something bad was about to happen.

So Apple had to take their generally true random algorithm and make it intentionally less random so it worked like people implicitly expected it to. Makes me wonder how many things we really are "holding wrong" because dev expectations didn't line up with how people actually use something.

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

"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.

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.

Who said anything about hands? I'm trying to make an analogy between shuffling a deck and shuffling xkcd comics. I thought having a visual, physical analogue would perhaps help in seeing that randomness still exists in a shuffle.

Sorry, the point I was trying to make was "shuffle" could possibly mean "re-shuffle after every track" - so you could still get the same track twice in a row.

(It was a bad way of stating it, that's on me)

Shuffling the whole playlist to choose a new song every time is no different than choosing uniformly from all songs every time. What would be the point? I can't tell what you are getting at.

My point is that, for a not-unreasonable interpretation of "shuffle", it is the same as "random".

nvm

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.

Grabbing a new song with probabilities weights based on past outcomes is just as "truly random" as picking a new song with a uniform distribution on all songs every time. https://en.wikipedia.org/wiki/Stochastic_process

> What people really want with their song shuffle is something new they haven't played in a while. Speak for yourself

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.

People are pattern seeking, even in "random" data.

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%).

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...

Reminds me of Spotify's post about shuffling songs: https://engineering.atspotify.com/2014/02/how-to-shuffle-son...

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.

The new Baldur's Gate game has a setting called "karmic dice", where it apparently biases the dice rolls to not cause repeated outcomes as much (i.e. if you're passing checks a lot, it will start to bias towards lower results, and if you're failing checks a lot, it will start to bias towards higher results). They devs made the interesting decision to have that setting on by default, which I'm guessing is based on the experience they expect more players to want. Regardless of my own preference, I think it's pretty cool they made that an explicit setting that players can choose to keep on or turn off.

I was once tasked with creating a DVD game that was meant to randomly pick questions from its available pool. Learned lots of things about how unrandom random can be. On the lower end of DVD players, there was a stored list of values between 0 and maxInt that was randomized when created. Each call of the random function would just move the pointer to the next item in the list. This meant that it would essentially play the questions in the same order every time. I can't remember the specifics if the list was reset when loading a disc or when the player was turned on.

Turns out, the company wanting the game got scarred of some patent that invoked the word random, so we had to reprogram the thing essentially do the same as that player. We had multiple sequences of randomized questions, and the game pick one of the sequences to play back in order when started.

This reminds me of an mp3 CD player I had. I don't remember if the feature was called shuffle or random, but it played the same sequence of tracks every time. I could only fully enjoy it once per CD.

I had a CD player in my SUV that had the same problem. The only saving grace is that it could play mp3s from the CD, so I had mixes that had 100 songs on them.

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 not that badly [3]

[1] https://fuglede.dk/en/blog/bias-in-net-rng/

[2] https://arxiv.org/abs/2310.04153

[3] https://gist.github.com/fuglede/772402ecc3997ada82a03ce65361...

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.

It will have to stay a mystery, looking at distribution, both algorithms looked the same.

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.

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.

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

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.

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 )

The real question is how uniform the randomness is.

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).

Maybe they use their own random number generator. https://xkcd.com/221/

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 <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.

> a random stream of bits should have almost as many ones as zeros

almost??

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.

But in absolute (not relative terms) the counts will tend to diverge over time.

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.

In the limit, yes.

But for the first few bits maybe "almost".

With n random bits, you will likely have approximately \sqrt{n} more ones than zeros (or vice versa).

You aren't suggesting that something random should be predictable, right?

"Almost" suggests it is predictably fewer

"Around" might be better

It suggests roughly the same amount, could be higher or lower.

Around would do that more effectively. Almost is more similar to nearly, and I agree commonly used for lower.

I read "almost as many" as "not quite as many". In other words, fewer.

My mental model is that an unbiased random stream of 1's and 0's should converge on 50% 1's and 50% 0's over time, not 49% 1's and 51% 0's.

Looks like it's a language ambiguity thing I'm not quite getting.

Over time, it should be almost 50/50, yeah. What if you got 10000001 random numbers? There's no way it's exactly 50/50 with an uneven amount. It's almost 50/50

To converge on 50% implies 49%\51% prior. Almost even.

Yes, almost. They will approach equal as the count approaches infinity.

So if ypu ever see a random pick equate to 50/50, the end of the universe is upon us.

The ratio of occurrences of 0s and 1s will go to one in the limit. But the absolute difference of occurrences will diverge. (It grows roughly like the square-root of the number of digits.)

Nit, their ratio (bits set/unset) will approach 1 as the count approaches infinity, but the values themselves will not approach equal. https://gist.github.com/AlexAltea/3aa96efc41f59e80631c346908...

If a random streams length is odd, they'll never be the exact same.

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 :)

Sometimes the random button should just return 4 multiple times in a row, as a reference to https://xkcd.com/221/

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.

Reply on news.ycombinator.com