## Don’t listen to the numbers!

Mark Chu-Carrol has written this post discussing this silliness about “spooky” patterns in the digits of $\pi$, $\sqrt 2$ and some other number, derived from $\pi$. I’d recommend reading Mark CC’s piece, including the comments, which contain a discussion about what sounds like a non-silly use of this sort of pattern spotting that (it is claimed) has historically been used in mystical traditions – namely seeing what the patterns your brain pulls out tell you about your brain. The guy being discussed doesn’t do that. He thinks that the patterns were left by a (“Pythagorean“) god to tell us stuff. As one commenter pointed out, this is the sort of thinking that leads to murdering John Lennon.

Anyway, I thought it might be a good time to talk about the mathematics of patterns showing up everywhere, and how it is way cooler than any supernatural pseudo-explanation. One kind of “patterns are inevitable” result is Ramsey theory. Taking one of the simplest examples here, draw six points on a piece of paper (arranged as a regular hexagon, say), and then take a red pen and a blue pen. Now, draw lines (each with one of the two pens but changing pen whenever you wish) joining together each pair of dots. Amongst your lines there must be a triangle all of one colour. Furthermore if we have any picture we want to find amongst coloured lines joining dots (with any finite number of colours) we only need to insist that there be more than some given number of dots and we can be sure of it. There are many similar results about absolutely guaranteeing structure in a large enough finite set.

OK, well that’s combinatorics, something I don’t actually know to much about. Also, it’s not obviously related to patterns in $\pi$. So let’s talk about measure theory and, since it’s more intuitive, let’s disguise it as probability. Consider the uniform distribution on an interval. We claim the following.

1. Fix a finite string of digits (in a fixed base n) and choose a number at random from our interval. The probability that the number we choose contains our string (in its base n expansion) is 1.

We can “bootstrap” this result up to the following infinitely awesome fact.

2. Choose a number at random from an interval. With probability 1, its expansion in every base will contain every finite string of characters in that base infinitely many times.

There are sketches of the proofs of these at the bottom of the page together with a note about what “probability 1″ implies.
The stronger condition of normality (roughly that each string of a particular length comes up with the same frequency) is also true with probability 1.

Why this is unimaginably cool
Lets think about this property that is so amazingly common amongst numbers. Forget about the short patterns in base ten that the kook at the start had; think about base 27. Use the letters of the alphabet and a space as the symbols for digits. What kind of structure does the expansion of our randomly chosen number almost certainly have? Well, if you are looking for beauty, the complete works of Shakespeare will be there, and of Goethe, CamĂµes, Tolstoy, Cervantes and Moliere. If you want guidance, there will be the King James Bible, the Koran, the Book of Mormon, Dianetics(tm), das Kapital and Atlas Shrugged. It will also contains versions of these books interspersed with snarky comments mocking the ideas contained therein.

It contains this blog post. It contains a detailed description of what you did today. It contains a detailed description of what you will do tomorrow (spooky, huh?). It contains the lost plays of Sophocles and the folk tales of extinct oral traditions and every beautiful story and poem that never got written (as well as rather a lot of meaningless strings of letters and spaces).

Or how about base 2. Big strings of zeroes and ones are, as you no doubt know, what tell computers what to do. So we have plain text files of all the books mentioned above as well as nice illustrated pdfs of each and mp3s of them being read in the voice of your favourite actor. We also have every flash video file on YouTube, and flash videos of every film you ever loved or hated and everything that ever happened anywhere (as well as nice DVD versions). It also contains video of things that didn’t happen. It has Richie Edwards and Lord Lucan racing on unicorns, and Frank Sinatra singing Rufus Wainwright songs. It contains an arbitrarily accurate physical model of the universe, predicting the location of each subatomic particle (including those in your brain) into the ridiculously far future, and others describing other possible universes equally precisely.

My point is, there is a lot of structure in nearly every number. This is very cool. It also means that if you find patters in a number it doesn’t mean that the number is trying to talk to you. It’s a number; they aren’t known for being very chatty. In any case, if it were talking to you, it would (with probability 1) say every imaginable stupid thing and keep contradicting itself. Don’t listen to the numbers!

A word on “with probability 1″
Counter-intuitive things end up being true when you talk about infinite sets (like “there are as many primes as natural numbers”). One of these is that “the probability of E occurring is 1″ is not the same as “E is certain to occur”. Equivalently, “the probability of E occurring is 0″ is not the same as “E is impossible”. The most obvious example to think of is the probability of any one specified number being chosen. Since the distribution is uniform (and we have infinitely many points) this has to be zero (otherwise the probability of “we pick any number” would end up being infinity rather than 1; for the details read about measure theory). However we have to pick some number, so clearly this is not impossible. Perhaps the best way of thinking about it is that a zero probability event occurring (or equivalently a probability 1 event failing to occur) is that an arbitrarily pessimistic person need not worry about it. That is even if given a ridiculously small fixed probability of something occuring (such as the probability according to quantum mechanics that you will simply vanish from existence in the next minute) still bothers you, you don’t have to worry about the probability zero event; it’s infinitely less likely than anything that is merely unlikely.

Sketches of proofs
In the following “length” is really 1 dimensional Lebesgue measure. If you want to know that everything I am doing is formally allowed, you will have to know a bit a measure theory.
Vague sketch of a proof 1NB some formulas failed to parse so I took out the “$” marks. Can anyone see what is wrong? For simplicity we shall assume our interval is the half-open [0,1); the general version is similar. The proof of this is very like the proof that the Cantor set has measure 0 (indeed the special case where the base is 3 and the string we want to avoid is (2) exactly this). Let the base be b and the string be $s=(s_1,\dots s_n)$ (where n is the length of s). We shall show that a subset of [0,1] with measure 0 that contains every number that doesn’t have s in it’s base b expansion. Let $A_1$ be the set obtained from [0,1) by removing the half open interval latex [0.s_2\dots s_n 00\dots ,s_1\dots s_n(b-1)(b-1)\dots). The removed interval has length $b^{-n}$ so the length of $A_1$ is $1-b^{-n}$ or $\frac {b^n-1 }{b^n}$. Also the removed interval contains only numbers whose base b expansion contains s (straight after the point). Note that $A_1$ can be broken up into b^n-1 intervals of length $b^{-n}$ of the following form latex [0 . a_1 \dots a_n 00\dots , a_1\dots a_n(b-1)(b-1) \dots), where $(a_1,\dots, a_n)$ is any of the b^n-1 strings of length n which are not s. We remove from each of these intervals the a smaller interval, namely latex [0. a_1\dots a_n s_1\dots s_n 0 0 \dots ,a_1 \dots a_n (b-1) (b-1) \dots). We call the set obtained by removing all these small intervals from $A_1$, $A_2$. Each of the removed intervals has length $b^{-(n+1)}$. Hence we have left the proportion $1-b^{-n}$ of each of the bigger intervals and so the length of $A_2$ is $1-b^{-n}$ times the length of$A_1$, that is $(1-b^{-n})^2$. Note we have only removed for [0,1) numbers whose expansion contains the string s (start either straight after the point or n places after the point) so all numbers without s in their expansion are in $A_2$. We continue in this fashion, breaking our set into intervals and removing a small interval containing only numbers with the string s in their expansion to get sets$late A_n\$ for each positive integer n such that all numbers without s in their expansion are in each $A_n$ and the length of $A_n$ is $(1-b^{-n})^n$. Now we assume, for contradiction, that the length of the set of numbers without s in their expansion is positive; we call it l . Provided only that we pick n large enough,
$(1-b^{-n})^n$ is less than l. Thus the length of $A_n$ is less than l. Since the set of all numbers without s in their expansion is contained in $A_1$ it follows that the length of this set is less than l. This contradicts our choice of l. Hence the length of the set of all numbers missing s from their base b expansions must be 0.
end of sketch

Vague sketch of proof of 2
We obtain this from the previous result using the fact that the union of countably many set of length 0 has length 0. There are only countably many finite strings in any base so the set so the set of numbers missing any string in a given base is the countable union (indexed by the set of such strings) of the sets which miss each sting. We showed already that this has 0 length. Hence the set of all numbers missing any finite string in a single base has length 0. Now the set of numbers missing any string in any base is the countable union (indexed by b) of those missing a string in base b. Hence this also has length 0. A number which contains every string necessarily contains each string infinitely many times because each string is contained in infinitely many different longer strings. The result follows.