In mathematics, a real number is said to be simply normal in an integer base b[1] if its infinite sequence of digits is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b.
A number is said to be normal in base b if, for every positive integer n, all possible strings n digits long have density b−n.
Intuitively, a number being simply normal means that no digit occurs more frequently than any other.
A normal number can be thought of as an infinite sequence of coin flips (binary) or rolls of a die (base 6).
Even though there will be sequences such as 10, 100, or more consecutive tails (binary) or fives (base 6) or even 10, 100, or more repetitions of a sequence such as tail-head (two consecutive coin flips) or 6-1 (two consecutive rolls of a die), there will also be equally many of any other sequence of equal length.
It is widely believed that the (computable) numbers √2, π, and e are normal, but a proof remains elusive.
[3] Let Σ be a finite alphabet of b-digits, Σω the set of all infinite sequences that may be drawn from that alphabet, and Σ∗ the set of finite sequences, or strings.
For each a in Σ let NS(a, n) denote the number of times the digit a appears in the first n digits of the sequence S. We say that S is simply normal if the limit
Now let w be any finite string in Σ∗ and let NS(w, n) be the number of times the string w appears as a substring in the first n digits of the sequence S. (For instance, if S = 01010101..., then NS(010, 8) = 3.)
where |w| denotes the length of the string w. In other words, S is normal if all strings of equal length occur with equal asymptotic frequency.
Roughly speaking, the probability of finding the string w in any given position in S is precisely that expected if the sequence had been produced at random.
Suppose now that b is an integer greater than 1 and x is a real number.
Consider the infinite digit sequence expansion Sx, b of x in the base b positional number system (we ignore the decimal point).
The real number x is rich in base b if and only if the set {x bn mod 1 : n ∈ N} is dense in the unit interval.
[11][12] We defined a number to be simply normal in base b if each individual digit appears with frequency 1⁄b.
[7][13] The concept of a normal number was introduced by Émile Borel (1909).
Becher and Figueira (2002) proved that there is a computable absolutely normal number.
Although this construction does not directly give the digits of the numbers constructed, it shows that it is possible in principle to enumerate each digit of a particular normal number.
Champernowne's constant obtained by concatenating the decimal representations of the natural numbers in order, is normal in base 10.
Harold Davenport and Erdős (1952) proved that the number represented by the same expression, with f being any non-constant polynomial whose values on the positive integers are positive integers, expressed in base 10, is normal in base 10.
Nakai and Shiokawa (1992) proved that if f(x) is any non-constant polynomial with real coefficients such that f(x) > 0 for all x > 0, then the real number represented by the concatenation where [f(n)] is the integer part of f(n) expressed in base b, is normal in base b.
The authors also show that the same result holds even more generally when f is any function of the form where the αs and βs are real numbers with β > β1 > β2 > ... > βd ≥ 0, and f(x) > 0 for all x > 0.
It has been an elusive goal to prove the normality of numbers that are not artificially constructed.
It has not even been proven that all digits actually occur infinitely many times in the decimal expansions of those constants (for example, in the case of π, the popular claim "every string of numbers eventually occurs in π" is not known to be true).
However, no irrational algebraic number has been proven to be normal in any base.
Martin (2001) gives an example of an irrational number that is absolutely abnormal.
Then α is a Liouville number and is absolutely abnormal.
Therefore: Ziv and Lempel showed: (they actually showed that the sequence's optimal compression ratio over all ILFSCs is exactly its entropy rate, a quantitative measure of its deviation from normality, which is 1 exactly when the sequence is normal).
Compare this with the algorithmically random sequences, which are those infinite sequences that appear random to any algorithm (and in fact have similar gambling and compression characterizations with Turing machines replacing finite-state machines).
is equidistributed modulo 1,[21][22] or equivalently, using Weyl's criterion, if and only if