How random is xkcd? (2015)

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.

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

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.

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