# How Random is xkcd? – Comfortably Numbered

*by*Phil Tadros

A blatant abuse of statistics.

#### Friday, March 20, 2015 · 6 min learn

Apparently Randall Munroe will get loads of messages saying that the “random”

button on xkcd is biased.

2015-03-19 16:47:00

Hobzadditionally, Randall, the random button on the xkcd

frontpage is frustratingly un-random2015-03-19 18:50:52

~Randallit’s random.2015-03-19 18:50:59

~Randallindividuals contact me continuously to inform me

that it’s not2015-03-19 18:51:17

~Randallwhich is a pleasant illustration of that psychological

bias we’ve got

I believed I might perform a little investigating to see simply how random xkcd is.

Making constantly random numbers (sure, that sounds bizarre) is basically vital

in issues like cryptography. Unrandom random numbers can cripple an in any other case

safe community. So there’s a surprisingly great amount of labor devoted to

randomness.

There are providers like random.org which delight

themselves on randomness, and HotBits,

which helps you to order random bytes which might be generated from radioactive decay. A

lot of functions use `/dev/urandom/`

, which is an OS-level random generator

that makes use of all kinds of sources of entropy equivalent to community noise, CPU warmth, and

the present climate in Kansas.

Sadly, it’s *actually* laborious to inform whether or not numbers are random or not.

After all, patterns can creep into random

numbers. However extra annoyingly, a

obviously apparent sample would possibly simply be unintended. My favourite instance of this

is the Feynman Point, which is a

sequence of a number of 9s that seems someplace within the (very unpredictable) decimal

enlargement of pi.

There are a bunch of established methods to check the randomness of a random quantity

generator (such because the excitingly-named Diehard

tests). All of them check for options

that ostensibly random knowledge ought to have. For instance, a random stream of bits

ought to have nearly as many ones as zeros. Not all exams are that apparent,

although, and statistics could be very slippery and unintuitive when it seems like

it.

NIST (the Nationwide Institute of Requirements and Expertise, who take care of issues

like how lengthy an inch is and learn how to backdoor elliptic curves)

publishes

an ordinary for randomness based mostly on such exams, and distributes software program that

runs these exams on datasets.

I wrote a Python program to obtain 10,000 xkcd-random numbers (yay

`requests`

!), and transformed them into bitstrings. Then, I fed them to the NIST

Statistical Take a look at Suite.

The outcomes are beneath:

```
------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
generator is <knowledge/knowledge.xkcd.lengthy>
------------------------------------------------------------------------------
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST
------------------------------------------------------------------------------
5 8 7 13 9 8 13 12 15 10 0.437274 100/100 Frequency
10 10 11 9 10 16 10 6 8 10 0.759756 99/100 BlockFrequency
5 12 13 10 7 10 10 10 9 14 0.699313 100/100 CumulativeSums
8 3 13 9 9 14 13 8 12 11 0.366918 98/100 CumulativeSums
8 12 11 3 9 8 17 12 9 11 0.224821 100/100 Runs
7 8 8 6 15 9 12 9 15 11 0.437274 99/100 LongestRun
7 8 7 16 0 25 0 25 0 12 0.000000 * 100/100 FFT
3 10 4 19 15 0 18 6 10 15 0.000009 * 100/100 Serial
9 14 10 2 14 8 6 10 16 11 0.080519 100/100 Serial
16 1 5 9 6 0 6 0 10 47 0.000000 * 93/100 * LinearComplexity
```

The vital column right here is “Proportion”, which reveals the move charge. They’re

all stellar.

If that isn’t convincing, I ran an clearly nonrandom pattern for comparability.

That is what NIST’s STS thinks of the primary 100,000 bits of Mission Gutenberg’s

plaintext version of

*Romeo and Juliet*:

```
------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
generator is <knowledge/knowledge.rnj>
------------------------------------------------------------------------------
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST
------------------------------------------------------------------------------
95 3 0 1 0 0 1 0 0 0 0.000000 * 25/100 * Frequency
55 14 10 6 6 3 1 1 3 1 0.000000 * 64/100 * BlockFrequency
94 3 1 0 0 1 1 0 0 0 0.000000 * 28/100 * CumulativeSums
93 4 1 1 0 0 0 0 1 0 0.000000 * 30/100 * CumulativeSums
51 7 10 10 4 4 2 5 2 5 0.000000 * 61/100 * Runs
90 8 1 1 0 0 0 0 0 0 0.000000 * 44/100 * LongestRun
92 2 2 2 0 1 0 1 0 0 0.000000 * 23/100 * FFT
100 0 0 0 0 0 0 0 0 0 0.000000 * 0/100 * Serial
100 0 0 0 0 0 0 0 0 0 0.000000 * 0/100 * Serial
14 2 2 7 11 0 4 0 11 49 0.000000 * 95/100 * LinearComplexity
```

A lot worse.

I encourage you to play with the STS code. It allows you to do all kinds of different

neat issues, like testing bitstrings for frequent “templates” and reporting if

too many are discovered. It additionally segfaults all over, which is definitely

very disturbing contemplating that it’s technically a part of the US authorities’s

laptop safety challenge.

In any case, we’ve established that xkcd’s random generator in all fairness

unpredictable and unbiased. Because it occurs, they’re utilizing the Mersenne Tornado,

which is a well-established pseudorandom technology algorithm.

So why does the random quantity technology seem so biased after we’re idly

refreshing on lazy Sunday nights? A part of it’s, after all, human nature. We

wish to see patterns in every single place.

However right here’s a extra concrete, mathematical clarification. The conceptual thought is

that to start with, hitting “random” is likelier to hit an unread comedian, however

when you’ve seen increasingly of them, you get repeats. Let’s attempt to quantify

this: we’re going to calculate the *anticipated worth* of the variety of instances you

must hit “random” till you could have seen each single comedian. You will have seen

this downside within the context of “what number of instances do it’s essential to roll a die till

you could have rolled all six faces no less than as soon as?”.

Expected value is the common

worth of some random variable in the event you do an experiment a number of instances. For

instance, in the event you roll a die gazillions of time, the common quantity you’ll get is

$ (1+2+3+4+5+6)/6 = 3.5 $, in order that’s the *anticipated* worth.

We’re going to calculate the anticipated variety of instances you hit “random” by

calculating the variety of instances it’s essential to hit it to get the primary, second,

third, and (on the whole) nth distinctive comedian. Then, due to a helpful property of

anticipated values, we will simply add them collectively till $ n = 1500 $ (there are

1500 comics revealed as of proper now) to see how lengthy, as of right this moment, this

course of would take.

When you’re searching for your $ n $th unread comedian, every time you hit “random”

you could have a $ 1 – n/1500 $ likelihood of getting a contemporary one. It is a geometric

probability distribution,

which is Math for “you retain making an attempt one thing with a relentless chance till

it succeeds”. For geometric chance distributions, the anticipated worth is

one over the chance (although I’m not going to show it right here, this

intuitively is sensible: you’ll count on to need to roll a die round 6 instances

till you get your first 1, or to flip a coin twice till you get your first

heads).

Anyhow, for the nth comedian, the anticipated variety of clicks is $ 1500/(1500-n) $. Including

these up for every $ n $, we’ve got this monstrosity:

This works out to, on common, 11836 clicks. That’s loads of clicks.

As frequent sense dictates, the extra instances you could have clicked “random”, the much less

seemingly it’s so that you can hit a brand new comedian. And that’s why Randall’s random button

appears biased.

Yet one more little bit of statistics: in the event you’ve taken a chance class, you may need

heard of the birthday downside. That’s, say you could have a celebration with $ n $ individuals.

What’s the chance that some pair of individuals on the occasion share a birthday?

It seems that when you’ve got simply 23 individuals, the chance is already 50-50.

That is considerably counterintuitive; most birthday events solely have one birthday

boy! The fallacy is that the issue isn’t asking if some *specific* particular person

shares a birthday with another person. It’s asking if *any* two individuals share a

birthday.

The birthday “paradox” seems to be vital in cryptography, particularly

when searching for hash collisions. The variety of hashes it’s essential to generate

earlier than you hit a collision is just like the variety of individuals you want at a

occasion earlier than some pair shares a birthday—a lot smaller than what you’ll

count on.

By way of xkcd-surfing, this helps reply the query “what number of instances will I

hit random earlier than I see a repeat?”.

There are many good explanations for the maths behind the birthday downside

on-line (Wolfram Mathworld

and Wikipedia)—however in the event you

don’t imagine the quantity 23 quoted above, it’s value spending a while making an attempt

to unravel it your self simply to know what’s actually happening (it’s not laborious).

I’m simply going to dump the components right here with none clarification.

For 1500 comics, the chance that you simply get a repeat after $ okay $ clicks is:

[ 1 – frac{1500!}{(1500-k)!1500^k} ]Throwing this at WolframAlpha, we see that after solely 45 clicks, you could have a

50-50 likelihood of seeing a reproduction comedian. Put a distinct manner, *there are even
odds that the final 45 comics you could have seen comprise a reproduction pair someplace
in there*.

So we’ve empirically validated that xkcd’s RNG is as shut as we will count on for

one thing statistically random. We’ve additionally seen two the explanation why it feels

biased.

However on a deeper and way more vital degree, we’ve seen how counterintuitive

and messy the random-number enterprise is, and the way statistical information can trick us

into seeing patterns that aren’t there.

P.S. My methodology for these experiments most likely not the very best, since I’ve

no formal statistics background. If you wish to take a look at the code used or a

dump of my dataset, depart a remark beneath and I’ll ship it to you.