In mathematics, a normal number is, roughly speaking, a real number whose digits (in every base) show a uniform distribution, with all digits being equally likely, all pairs of digits equally likely, all triplets of digits equally likely, etc. For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... The radix (Latin for root), also called base, is the number of various unique symbols (or digits or numerals) a positional numeral system uses to represent numbers. ... In probability theory and statistics, the discrete uniform distribution is a discrete probability distribution that can be characterized by saying that all values of a finite set of possible values are equally probable. ...

While a general proof can be given that "almost all" numbers are normal, this proof is not constructive and only very few concrete numbers have been shown to be normal. It is for instance widely believed that the numbers √2, π and e are normal, but a proof remains elusive. In mathematics, the phrase almost all has a number of specialised uses. ... The square root of 2 is equal to the length of the hypotenuse of a right triangle with legs of length 1. ... When a circles diameter is 1, its circumference is Ï€. Pi or Ï€ is the ratio of a circles circumference to its diameter in Euclidean geometry, approximately 3. ... e is the unique number such that the value of the derivative of f (x) = ex (blue curve) at the point x = 0 is exactly 1. ...

Definitions

Let Σ be a finite alphabet of b digits. Let be an infinite sequence drawn from the alphabet Σ. Let be a finite string drawn from the alphabet Σ. Let n be a positive integer. Define N_S(w,n) to 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 N_S(010, 8) = 3.) S is normal if, for all finite strings , In computer science, an alphabet is a finite set of characters or digits. ... For other senses of this word, see sequence (disambiguation). ... In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... A substring of a string is a string such that . ...

(where | w | denotes the length of the string w; see also limit.) 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. The limit of a sequence is one of the oldest concepts in mathematical analysis. ... In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. ... Probability is the likelihood that something is the case or will happen. ... A random sequence is a kind of stochastic process. ...

Suppose now that b is an integer greater than 1 and x is a real number. Consider the infinite digit sequence expansion S_{x, b} of x in the base b positional number system (we ignore the decimal point). We say x is normal in base b if the sequence S_{x, 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 positive integer b. The integers are commonly denoted by the above symbol. ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... This article is about different methods of expressing numbers with symbols. ...

A given infinite sequence is either normal or not normal, whereas a real number, having a different base-b expansion for each integer , may be normal in one base but not in another (Cassels 1959 and Schmidt 1960). John William Scott Cassels, FRS (born July 11, 1922 in Durham, UK) is a leading British mathematician. ... Wolfgang M. Schmidt is a mathematician. ...

Every normal number in base r is normal in base s if and only if log r / log s is a rational number. (Schmidt 1960)

A weaker property than normality is simple normality. A number is simply normal in base b if each individual digit appears with frequency 1/b.

Properties and examples

The concept of a normal number was introduced by Émile Borel in 1909. Using the Borel-Cantelli lemma, he proved the normal number theorem: almost all real numbers are normal, in the sense that the set of non-normal numbers has Lebesgue measure zero (Borel 1909). This theorem established the existence of normal numbers, but Waclaw Sierpinski in 1917 was the first to give an example of one. Félix Édouard Justin Émile Borel (January 7, 1871 – February 3, 1956) was a French mathematician and politician. ... In probability theory, the Borel_Cantelli lemma is a theorem about sequences of events. ... In mathematics, the phrase almost all has a number of specialised uses. ... In mathematics, the Lebesgue measure is the standard way of assigning a length, area or volume to subsets of Euclidean space. ... Wacław Franciszek Sierpiński, was born on March 14, 1882 in Warsaw and died on October 21, 1969 in Warsaw. ...

The set of non-normal numbers, even though "small" in the sense of being a null set, is "large" in the sense of being uncountable. Indeed, there are uncountably many numbers whose decimal expansion does not contain the digit 5, and none of these is normal. In measure theory, a null set is a set that is negligible for the purposes of the measure in question. ... In mathematics, an uncountable set is a set which is not countable. ...

Champernowne's number In mathematics, the Champernowne constant C10 is a certain real number, named after mathematician D. G. Champernowne. ...

0.1234567891011121314151617...,

obtained by concatenating the decimal representations of the natural numbers in order, is normal in base 10, but it might not be normal in some other bases. The Copeland–Erdős constant The Copeland-ErdÅ‘s constant is the concatenation of 0. ...

0.235711131719232931374143...,

obtained by concatenating the prime numbers in base 10, is also known to be normal in base 10. In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ...

No rational number is normal to any base, since the digit sequences of rational numbers are eventually periodic. In mathematics, a rational number is a number which can be expressed as a ratio of two integers. ...

An example of a normal number is given by Chaitin's constant . Indeed, every algorithmically random sequence over the alphabet is the base-b expansion of a normal number. A computable absolutely normal number was constructed in (Becher 2002). In the computer science subfield of algorithmic information theory the Chaitin constant or halting probability is a construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or programming language will halt. ... Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm. ... In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. ...

It has been an elusive goal to prove the normality of numbers which were not explicitly constructed for the purpose. It is for instance unknown whether √2, π, ln(2) or e is normal (but all of them are strongly conjectured to be normal, because of some empirical evidence). It is not even known which digits occur infinitely often in the decimal expansions of those constants. David H. Bailey and Richard E. Crandall conjectured in 2001 that every irrational algebraic number is normal; while no counterexamples are known, there also exists no algebraic number that has been proven to be normal in any base. The square root of two is the positive real number which, when multiplied by itself, gives a product of two. ... When a circles diameter is 1, its circumference is Ï€. Pi or Ï€ is the ratio of a circles circumference to its diameter in Euclidean geometry, approximately 3. ... The natural logarithm, formerly known as the hyperbolic logarithm, is the logarithm to the base e, where e is an irrational constant approximately equal to 2. ... e is the unique number such that the value of the derivative of f (x) = ex (blue curve) at the point x = 0 is exactly 1. ... In mathematics, an irrational number is any real number that is not a rational number — that is, it is a number which cannot be expressed as a fraction m/n, where m and n are integers, with n non-zero. ... In mathematics, an algebraic number is any number that is a root of an algebraic equation, a non-zero polynomial with integer (or equivalently, rational) coefficients. ...

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 disjunctive sequence is an infinite sequence (over a finite alphabet of characters) in which every finite string appears as a substring. ...

Additional properties of normal numbers include:

• Every positive number is the product of two normal numbers. This follows from the general fact that every number is the product of two numbers from a set if the complement of X has measure 0.
• If x is normal in base b and q is a rational number, then is normal in base b. (Wall 1949)

• If is dense (for every α < 1 and for all sufficiently large n, ) and are the base-b expansions of the elements of A, then the number , formed by concatenating the elements of A, is normal in base b (Copeland and Erdős 1946). From this it follows that Champernowne's number is normal in base 10 (since the set of all positive integers is obviously dense) and that the Copeland-Erdős constant is normal in base 10 (since the prime number theorem implies that the set of primes is dense).

• A sequence is normal if and only if every block of equal length appears with equal frequency. (A block of length k is a substring of length k appearing at a position in the sequence that is a multiple of k: e.g. the first length-k block in S is S[1..k], the second length-k block is S[k+1..2k], etc.) This was implicit in the work of Ziv and Lempel (1978) and made explicit in the work of Bourke, Hitchcock, and Vinodchandran (2005).

• A number is normal in base b if and only if it is simply normal in base b^k for every integer . This follows from the previous block characterization of normality: Since the n^th block of length k in its base b expansion corresponds to the n^th digit in its base b^k expansion, a number is simply normal in base b^k if and only if blocks of length k appear in its base b expansion with equal frequency.

• A number is normal if and only if it is simply normal in every base. This follows from the previous characterization of base b normality.

• The set of normal sequences is closed under finite variations: adding, removing, or changing a finite number of digits in any normal sequence leaves it normal.

In mathematics, a rational number is a number which can be expressed as a ratio of two integers. ... In number theory, the prime number theorem (PNT) describes the approximate, asymptotic distribution of the prime numbers. ... ↔ ⇔ ≡ logical symbols representing iff. ... In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ...

Connection to finite-state machines

Agafonov showed an early connection between finite-state machines and normal sequences: every subsequence selected from a normal sequence by a regular language is also normal. In other words, if one runs a finite-state machine on a normal sequence, where the finite-state machine outputs the digit it just read whenever it enters an accepting state, then the sequence it outputs will be normal. (Agafonov 1968) In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... A regular language is a formal language (i. ... Fig. ...

A deeper connection exists with finite-state gamblers (FSG's) and information lossless finite-state compressors (ILFSC's).

• A finite-state gambler (a.k.a. finite-state martingale) is a finite-state machine over a finite alphabet Σ, each of whose states is labelled with percentages of money to bet on each digit in Σ. For instance, for a FSG over the binary alphabet Σ = {0,1}, the current state q bets some percentage of the gambler's money on the bit 0, and the remaining q₁ = 1 − q₀ fraction of the gambler's money on the bit 1. The money bet on the digit that comes next in the input (total money times percent bet) is multiplied by | Σ | , and the rest of the money is lost. After the bit is read, the FSG transitions to the next state according to the input it received. A FSG d succeeds on an infinite sequence S if, starting from $1, it makes unbounded money betting on the sequence; i.e., if

  

  where is the amount of money the gambler d has after reading the first n digits of S (see limit superior).
• A finite-state compressor is a finite-state machine with output strings labelling its state transitions, including possibly the empty string. (Since one digit is read from the input sequence for each state transition, it is necessary to be able to output the empty string in order to achieve any compression at all). An information lossless finite-state compressor is a finite-state compressor whose input can be uniquely recovered from its output and final state. In other words, for a finite-state compressor C with state set Q, C is information lossless if the function , mapping the input string of C to the output string and final state of C, is 1-1. Compression techniques such as Huffman coding or Shannon-Fano coding can be implemented with ILFSC's. An ILFSC C compresses an infinite sequence S if

  

  where is the number of digits output by C after reading the first n digits of S. Note that the compression ratio (the limit inferior above) can always be made to equal 1 by the 1-state ILFSC that simply copies its input to the output.

Schnorr and Stimm showed that no FSG can succeed on any normal sequence, and Bourke, Hitchcock and Vinodchandran showed the converse. Therefore: A stopped Brownian motion as an example for a martingale In probability theory, a martingale is a stochastic process (i. ... In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting bounds on the sequence. ... In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... In Automata Theory, a state transition table is a table describing the transition function T of a finite automaton. ... (Redirected from 1-1) In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ... In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ... In the field of data compression, Shannon-Fano coding is a technique for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). ... Data compression ratio is a computer term used to quantify the reduction in data quantity produced by a data compression algorithm. ... In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting bounds on the sequence. ... In traditional logic Conversion is a form of immediate inference in which from a given categorical proposition another proposition is inferred which has as its subject the predicate of the original proposition, and has as its predicate the subject of the original proposition, with the quality of the proposition remaining...

A sequence is normal if and only if there is no finite-state gambler that succeeds on it.

Ziv and Lempel showed:

A sequence is normal if and only if it is incompressible by any information lossless finite-state compressor

(they actually showed that the sequence's optimal compression ratio over all ILFSC's is exactly its entropy rate, a quantitative measure of its deviation from normality, which is 1 exactly when the sequence is normal). Since the LZ compression algorithm compresses asymptotically as well as any ILFSC, this means that the LZ compression algorithm can compress any non-normal sequence. (Ziv Lempel 1978) Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ... LZ77 and LZ78 are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. ...

These characterizations of normal sequences can be interpreted to mean that "normal" = "finite-state random"; i.e., the normal sequences are precisely those that appear random to any finite-state machine. 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). Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm. ... For the test of artificial intelligence, see Turing test. ...

Connection to equidistributed sequences

A number x is normal in base b if and only if the sequence is equidistributed modulo 1, or equivalently, using Weyl's criterion, if and only if ↔ ⇔ ≡ logical symbols representing iff. ... In mathematics, a bounded sequence (s1, s2, s3, …) of real numbers is said to be equidistributed on an interval [a, b] if for any subinterval [c, d] of [a, b] we have i. ... In mathematics, in the theory of diophantine approximation, Weyls criterion states that a sequence of real numbers is equidistributed mod 1 if and only if for all non-zero integers we have: Therefore distribution questions can be reduced to bounds on exponential sums, a fundamental and general method. ...

References

• Agafonov, V. N. "Normal sequences and finite automata." Soviet Mathematics Doklady, 9:324-325, 1968.
• Bailey, D. H. and Crandall, R. E. "On the Random Character of Fundamental Constant Expansions." Experimental Mathematics 10, 175-190, 2001. online version
• Becher, V. and Figueira, S. "An example of a computable absolutely normal number", Theoretical Computer Science, 270, pp. 947-958, 2002. online
• Borel, E. "Les probabilités dénombrables et leurs applications arithmétiques." Rend. Circ. Mat. Palermo 27, 247-271, 1909.
• Bourke, C. , Hitchcock, J. M., and Vinodchandran, N. V. "Entropy rates and finite-state dimension." Theoretical Computer Science, 2005.
• Cassels, J. W. S. "On a problem of Steinhaus about normal numbers." Colloquium Mathematicum, 7:95-101, 1959.
• Champernowne, D. G. "The Construction of Decimals Normal in the Scale of Ten." Journal of the London Mathematical Society 8, 254-260, 1933.
• Copeland A. H. and Erdős P. "Note on normal numbers." Bull. Amer. Math. Soc., (52):857-860, 1946.
• Schmidt, W. "On normal numbers." Pacific Journal of Mathematics, 10:661-672, 1960.
• Schnorr, C. P. and Stimm, H. "Endliche Automaten und Zufallsfolgen." Acta Informatica, 1:345-359, 1972.
• Sierpinski, W. "Démonstration élémentaire d'un théorème de M. Borel sur les nombres absolutment normaux et détermination effective d'un tel nombre." Bull. Soc. Math. France 45, 125-144, 1917.
• Wall. D. D. "Normal Numbers." Ph.D. thesis, University of California, Berkeley, California, USA, 1949.
• Ziv, J. and Lempel, A. "Compression of individual sequences via variable-rate coding." IEEE Transaction on Information Theory, 24:530-536, 1978.

Further reading

• Quéfflec, Martine (2006). "Old and new results on normality". IMS Lecture Notes--Monograph Series 48: 225–236.