normal number

With regard to real numbers:

A real number x is normal in base b if in its representation in base b all digits occur, in an asymptotic sense, equally often. In addition, for each m, the b^m different m-strings must occur equally often. In other words, lim n->infinity N(s,n)/n = b^-m for each m-string s, where N(s,n) is the number of occurrences of s in the first n base-b digits of x. A number that is normal in all bases is called normal.

Often a person will ask whether the decimal expansion of some real number is truly random. This is a misguided question when applied to such mathematical constants as pi; since they are by definition not random. The question is rather whether or not they are distinguishable by inspection from a truly random number sequence, and whether or not it is normal is one part of answering that question. This concept was formalized by E. Borel in 1909, who also proved that there are lots and lots of normal numbers. The conjecture that pi is normal remains unproven, though it is widely believed and has held true for all digits yet computed.

A real number is called normal if you can "find" all (finite) digit sequences in its expansion. There are several variant definitions in use, and often it's important to determine which is relevant.

First, there's the question of how often each sequence must occur.

• Easiest is the demand that the digit sequence just occur anywhere in the expansion of the number.
• Next, we can demand that the digit sequence appear infinitely many times in the expansion.
• Finally, we can demand that the digit sequence appear with the same density it would have in a truly random independent sequence of digits (for decimal, this means every digit sequence of length k appears with density 10^-k).

Additionally, there's a question of bases:

• We can demand any of the above in base 10 (decimal) only (or in binary, or in some other prespecified base), - OR -
• We can demand the above in every base.

No matter which choice we make, almost every real number turns out to be normal. So a randomly chosen number in the interval [0,1) is normal with probability 1. But proving a number is normal is usually very hard; we only know of a few explicitly-constructed examples that are normal.

Note that rational numbers have a cyclic expansion in every base, so they're never normal.

AxelBoldt asks me to mention Gregory Chaitin's Omega. Chaitin's Omega Ω, for any Turing complete system, is normal (by all definitions). The proof by hand waving for this is that if it were not, you could make statistical judgements of Turing machines. Unfortunately, it's also the consummate example of an "unconstructable" number (for the exact same reasons), so how important this is is debatable.

An example of a nonrepeating positional representation (necessarily representing an irrational number) that is not normal.

sum (n = 1..infinity, b^-n(n+1)/2)

That is,

.101001000100001000001000000100000001000000001...

The sequence contains only zeroes and ones, so it's obviously not normal when interpreted for any base larger than two; and since the sequence can never contain 11, it can't be normal for base 2 either.

Because of this, we know there is a chain of subset relations:

Integers < Rationals < Non-normals < Reals

I don't think anything is known about the normality of irrational real algebraic numbers; it would be nice to stick them in the middle of this chain.

The Infinite Monkeys Theorem (That monkeys randomly pounding on keyboards would eventually produce shakespeare, or any other famous work) is equivalent to saying that "a random number in base 81 is a normal number". Base 81 because there are (numbers + upper and lowercase alphabet + ! @ # $ % & * ( ) - [ ] ; : ' " , . ?)

The fact that we automatically understand the idea behind the infinite monkeys theorem means that we also have an innate sense of what a normal number is.

3.53I5AB8P5FSA5JHK72I8ASC47WWZLA is the first few digits of pi in base 36. If you bumped that up to base 81, would it contain all works of literature? That is not known yet, and treated in is pi normal?