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 , , and e are normal, but a proof remains elusive.
Definitions
Let be a finite alphabet of -digits, the set of all infinite sequences that may be drawn from that alphabet, and the set of finite sequences, or strings. Let be such a sequence. For each in let denote the number of times the digit appears in the first digits of the sequence . We say that is simply normal if the limit
for each . Now let be any finite string in and let be the number of times the string appears as a substring in the first digits of the sequence . (For instance, if , then .) is normal if, for all finite strings ,
where denotes the length of the string . In other words, 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 ), and each occur with frequency ; , , , and each occur with frequency ; , , , , , , , and each occur with frequency ; etc. Roughly speaking, the probability of finding the string in any given position in is precisely that expected if the sequence had been produced at random.
Suppose now that is an integer greater than 1 and is a real number. Consider the infinite digit sequence expansion of in the base positional number system (we ignore the decimal point). We say that is simply normal in base if the sequence is simply normal and that is normal in base if the sequence is normal. The number is called a normal number (or sometimes an absolutely normal number) if it is normal in base for every integer greater than 1.
A given infinite sequence is either normal or not normal, whereas a real number, having a different base- expansion for each integer , may be normal in one base but not in another (in which case it is not a normal number). For bases and with rational (so that and ) every number normal in base is normal in base . For bases and with 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 is one whose expansion in base 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 is rich in base , but not necessarily conversely. The real number is rich in base if and only if the set is dense in the unit interval.
We defined a number to be simply normal in base if each individual digit appears with frequency . For a given base , a number can be simply normal (but not normal or -dense,) -dense (but not simply normal or normal), normal (and thus simply normal and -dense), or none of these. A number is absolutely non-normal or absolutely abnormal if it is not simply normal in any base.