Random sequence
Encyclopedia
The concept of a random sequence is essential in probability theory
and statistics
. The concept generally relies on the notion of a sequence of random variable
s and many statistical discussions begin with the words "let X1,...,Xn be independent random variables...". Yet as D. H. Lehmer stated in 1951: "A random sequence is a vague notion... in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests traditional with statisticians".
Axiomatic probability theory
deliberately avoids a definition of a random sequence. Traditional probability theory does not state if a specific sequence is random, but generally proceeds to discuss the properties of random variables and stochastic sequences assuming some definition of randomness. The Bourbaki school considered the statement "let us consider a random sequence" an abuse of language. During the 20th century various technical approaches to defining random sequences were developed and now three distinct paradigms can be identified.
was one of the first mathematicians to formally address randomness in 1909. In 1919 Richard von Mises gave the first definition of algorithmic randomness, which was inspired by the law of large numbers, although he used the term collective rather than random sequence. Using the concept of the impossibility of a gambling system
, von Mises defined an infinite sequence of zeros and ones as random if it is not biased by having the frequency stability property i.e. the frequency of zeros goes to 1/2 and every sub-sequence we can select from it by a "proper" method of selection is also not biased.
The sub-sequence selection criterion imposed by von Mises is important, because although 0101010101... is not biased, by selecting the odd positions, we get 000000... which is not random. Von Mises never totally formalized his definition of a proper selection rule for sub-sequences, but in 1940 Alonzo Church
defined it as any recursive function
which having read the first N elements of the sequence decides if it wants to select element number N+1. Church was a pioneer in the field of computable functions, and the definition he made relied on the Church Turing Thesis for computability. This definition is often called Mises-Church randomness.
In 1966 Per Martin-Löf
introduced a new notion which is now generally considered the most satisfactory notion of algorithmic randomness. His original definition involved measure theory, but it was later shown that it can be expressed in terms of Kolmogorov complexity
. Kolmogrov's definition of a random string was that it is random if has no description shorter than itself via a universal Turing machine
.
Three basic paradigms for dealing with random sequences have now emerged:
In most cases, theorems relating the three paradigms (often equivalence) have been proven.
It is important to realize that for each of the definitions given above for infinite sequences, if one adds a billion zeros to the front of the random sequence the new sequence will still be considered random. Hence any application of these concepts to practical problems needs to be performed with care.
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
and statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
. The concept generally relies on the notion of a sequence of random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
s and many statistical discussions begin with the words "let X1,...,Xn be independent random variables...". Yet as D. H. Lehmer stated in 1951: "A random sequence is a vague notion... in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests traditional with statisticians".
Axiomatic probability theory
Probability axioms
In probability theory, the probability P of some event E, denoted P, is usually defined in such a way that P satisfies the Kolmogorov axioms, named after Andrey Kolmogorov, which are described below....
deliberately avoids a definition of a random sequence. Traditional probability theory does not state if a specific sequence is random, but generally proceeds to discuss the properties of random variables and stochastic sequences assuming some definition of randomness. The Bourbaki school considered the statement "let us consider a random sequence" an abuse of language. During the 20th century various technical approaches to defining random sequences were developed and now three distinct paradigms can be identified.
Early history
Émile BorelÉmile Borel
Félix Édouard Justin Émile Borel was a French mathematician and politician.Borel was born in Saint-Affrique, Aveyron. Along with René-Louis Baire and Henri Lebesgue, he was among the pioneers of measure theory and its application to probability theory. The concept of a Borel set is named in his...
was one of the first mathematicians to formally address randomness in 1909. In 1919 Richard von Mises gave the first definition of algorithmic randomness, which was inspired by the law of large numbers, although he used the term collective rather than random sequence. Using the concept of the impossibility of a gambling system
Impossibility of a gambling system
The principle of the impossibility of a gambling system is a concept in probability. It states that in a random sequence, the selection of sub-sequences does not change the probability of specific elements...
, von Mises defined an infinite sequence of zeros and ones as random if it is not biased by having the frequency stability property i.e. the frequency of zeros goes to 1/2 and every sub-sequence we can select from it by a "proper" method of selection is also not biased.
The sub-sequence selection criterion imposed by von Mises is important, because although 0101010101... is not biased, by selecting the odd positions, we get 000000... which is not random. Von Mises never totally formalized his definition of a proper selection rule for sub-sequences, but in 1940 Alonzo Church
Alonzo Church
Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
defined it as any recursive function
Recursive function
Recursive function may refer to:*Recursion , a procedure or subroutine, implemented in a programming language, whose implementation references itself*A total computable function, a function which is defined for all possible inputs...
which having read the first N elements of the sequence decides if it wants to select element number N+1. Church was a pioneer in the field of computable functions, and the definition he made relied on the Church Turing Thesis for computability. This definition is often called Mises-Church randomness.
Modern approaches
In the mid 1960s, A. N. Kolmogorov and D. W. Loveland independently proposed a more permissive selection rule. In their view Church's recursive function definition was too restrictive in that it read the elements in order. Instead they proposed a rule based on a partially computable process which having read any N elements of the sequence, decides if it wants to select another element which has not been read yet. This definition is often called Kolmogorov-Loveland randomness. But this method was considered too weak by Alexander Shen who showed that there is a Kolmogorov-Loveland stochastic sequence which does not conform to the general notion of randomness.In 1966 Per Martin-Löf
Per Martin-Löf
Per Erik Rutger Martin-Löf is a Swedish logician, philosopher, and mathematical statistician. He is internationally renowned for his work on the foundations of probability, statistics, mathematical logic, and computer science. Since the late 1970s, Martin-Löf's publications have been mainly in...
introduced a new notion which is now generally considered the most satisfactory notion of algorithmic randomness. His original definition involved measure theory, but it was later shown that it can be expressed in terms of Kolmogorov complexity
Kolmogorov complexity
In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
. Kolmogrov's definition of a random string was that it is random if has no description shorter than itself via a universal Turing machine
Universal Turing machine
In computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
.
Three basic paradigms for dealing with random sequences have now emerged:
- The frequency / measure-theoretic approach. This approach started with the work of Robert von Mises and Alonzo Church. In the 1960s Per Martin-Löf noticed that the sets coding such frequency-based stochastic properties are a special kind of measure zero sets, and that a more general and smooth definition can be obtained by considering all effectively measure zero sets.
- The complexity / compressibility approach. This paradigm was championed by A. N. Kolmogorov along with contributions Levin and Gregory ChaitinGregory ChaitinGregory John Chaitin is an Argentine-American mathematician and computer scientist.-Mathematics and computer science:Beginning in 2009 Chaitin has worked on metabiology, a field parallel to biology dealing with the random evolution of artificial software instead of natural software .Beginning in...
. For finite random sequences, Kolmogorov defined the "randomness" as the entropy, i.e. Kolmogorov complexityKolmogorov complexityIn algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
, of a string of length K of zeros and ones as the closeness of its entropy to K, i.e. if the complexity of the string is close to K it is very random and if the complexity is far below K, it is not so random.
- The predictability approach. This paradigm was due to Claus P. SchnorrClaus P. SchnorrClaus-Peter Schnorr is a distinguished German mathematician and cryptographer. He received his Ph.D. from the University of Saarbrücken in 1966, and his habilitation in 1970. Schnorr's contributions to cryptography include his study of Schnorr groups, which are used in the digital signature...
and uses a slightly different definition of constructive martingaleMartingaleMartingale can refer to:*Martingale , a stochastic process in which the conditional expectation of the next value, given the current and preceding values, is the current value*Martingale for horses...
s than martingales used in traditional probability theory. Schnorr showed how the existence of a selective betting strategy implied the existence of a selection rule for a biased sub-sequence.
In most cases, theorems relating the three paradigms (often equivalence) have been proven.
It is important to realize that for each of the definitions given above for infinite sequences, if one adds a billion zeros to the front of the random sequence the new sequence will still be considered random. Hence any application of these concepts to practical problems needs to be performed with care.
See also
- RandomnessRandomnessRandomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
- History of randomnessHistory of randomnessIn ancient history, the concepts of chance and randomness were intertwined with that of fate. Many ancient peoples threw dice to determine fate, and this later evolved into games of chance...
- Random number generator
- Seven states of randomnessSeven states of randomnessThe seven states of randomness in probability theory, fractals and risk analysis are extensions of the concept of normal distribution. These seven states were first introduced in by Benoît Mandelbrot in his 1997 book Fractals and scaling in finance which applied fractal analysis to the study of...
- Statistical randomnessStatistical randomnessA numeric sequence is said to be statistically random when it contains no recognizable patterns or regularities; sequences such as the results of an ideal dice roll, or the digits of π exhibit statistical randomness....
External links
- Video on frequency stability. Why humans can't "guess" randomly
- Randomness tests by Terry Ritter