In mathematics, a real number is said to be simply normal in an integer base b 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. If a number is normal, no finite combination of digits of a given length occurs more frequently than any other combination of the same length. 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. No digit or sequence is "favored". A number is said to be normal (sometimes called absolutely normal) if it is normal in all integer bases greater than or equal to 2. While a general proof can be given that almost all real numbers are normal (meaning that the set of non-normal numbers has Lebesgue measure zero), this proof is not constructive, and only a few specific numbers have been shown to be normal. For example, any Chaitin's constant is normal (and uncomputable). It is widely believed that the (computable) numbers √2, π, and e are normal, but a proof remains elusive.
Definitions 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. Let S ∈ Σω be such a sequence. 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
lim n → ∞ N S ( a , n ) n = 1 b {\displaystyle \lim _{n\to \infty }{\frac {N_{S}(a,n)}{n}}={\frac {1}{b}}}
for each a. 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.) S is normal if, for all finite strings w ∈ Σ∗,
lim n → ∞ N S ( w , n ) n = 1 b | w | {\displaystyle \lim _{n\to \infty }{\frac {N_{S}(w,n)}{n}}={\frac {1}{b^{|w|}}}}
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. For example, in a normal binary sequence (a sequence over the alphabet {0,1}), 0 and 1 each occur with frequency 1⁄2; 00, 01, 10, and 11 each occur with frequency 1⁄4; 000, 001, 010, 011, 100, 101, 110, and 111 each occur with frequency 1⁄8; etc. 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). We say that x is simply normal in base b if the sequence Sx, b is simply normal and that x is normal in base b if the sequence Sx, b is normal. The number x is called a normal number (or sometimes an absolutely normal number) if it is normal in base b for every integer b greater than 1. A given infinite sequence is either normal or not normal, whereas a real number, having a different base-b expansion for each integer b ≥ 2, may be normal in one base but not in another (in which case it is not a normal number). For bases r and s with log r / log s rational (so that r = bm and s = bn) every number normal in base r is normal in base s. For bases r and s with log r / log s irrational, there are uncountably many numbers normal in each base but not the other. A disjunctive sequence is a sequence in which every finite string appears. A normal sequence is disjunctive, but a disjunctive sequence need not be normal. A rich number in base b is one whose expansion in base b is disjunctive: one that is disjunctive to every base is called absolutely disjunctive or is said to be a lexicon. A number normal in base b is rich in base b, but not necessarily conversely. 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. We defined a number to be simply normal in base b if each individual digit appears with frequency 1⁄b. For a given base b, a number can be simply normal (but not normal or rich), rich (but not simply normal or normal), normal (and thus simply normal and rich), or none of these. A number is absolutely non-normal or absolutely abnormal if it is not simply normal in any base.
… excerpt ends here. Continue reading the full article.
