The concept of a random sequence is essential in
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
and
statistics
Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
. The concept generally relies on the notion of a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of
random variable
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
s and many statistical discussions begin with the words "let ''X''
1,...,''X
n'' 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.
Early history
Émile Borel
Félix Édouard Justin Émile Borel (; 7 January 1871 – 3 February 1956) was a French mathematician and politician. As a mathematician, he was known for his founding work in the areas of measure theory and probability.
Biography
Borel was ...
was one of the first mathematicians to formally address randomness in 1909. In 1919
Richard von Mises
Richard Edler von Mises (; 19 April 1883 – 14 July 1953) was an Austrian scientist and mathematician who worked on solid mechanics, fluid mechanics, aerodynamics, aeronautics, statistics and probability theory. He held the position of Gordo ...
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
The principle of the impossibility of a gambling system is a concept in probability. It states that in a random sequence, the methodical selection of subsequences does not change the probability of specific elements. The first mathematical demonst ...
, 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 (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scienc ...
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''.
Modern approaches
During the 20th century various technical approaches to defining random sequences were developed and now three distinct paradigms can be identified. 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 stochasticity''. 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 Erik Rutger Martin-Löf (; ; born 8 May 1942) 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 scie ...
introduced a new notion which is now generally considered the most satisfactory notion of
algorithmic randomness
Intuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequenc ...
. His original definition involved measure theory, but it was later shown that it can be expressed in terms of
Kolmogorov complexity
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...
. Kolmogorov's definition of a random string was that it is random if has no description shorter than itself via a
universal Turing machine
In computer science, a universal Turing machine (UTM) 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 simu ...
.
Three basic paradigms for dealing with random sequences have now emerged:
:* The ''frequency / measure-theoretic'' approach. This approach started with the work of Richard 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
In mathematical analysis, a null set N \subset \mathbb is a measurable set that has measure zero. This can be characterized as a set that can be covered by a countable union of intervals of arbitrarily small total length.
The notion of null s ...
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 from
Leonid Levin
Leonid Anatolievich Levin ( ; russian: Леони́д Анато́льевич Ле́вин; uk, Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American mathematician and computer scientist.
He is kn ...
and
Gregory Chaitin
Gregory John Chaitin ( ; born 25 June 1947) is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-t ...
. For finite sequences, Kolmogorov defines randomness of a binary string of length ''n'' as the entropy (or
Kolmogorov complexity
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...
) normalized by the length ''n''. In other words, if the Kolmogorov complexity of the string is close to ''n'', it is very random; if the complexity is far below ''n'', it is not so random. The dual concept of randomness is compressibility ‒ the more random a sequence is, the less compressible, and vice versa.
:* The ''predictability'' approach. This paradigm is due to
Claus P. Schnorr and uses a slightly different definition of constructive
martingales 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. If one only requires a recursive martingale to succeed on a sequence instead of constructively succeed on a sequence, then one gets the concept of recursive randomness.
Yongge Wang Yongge Wang (born 1967) is a computer science professor at the University of North Carolina at Charlotte specialized in algorithmic complexity and cryptography. He is the inventor of IEEE P1363 cryptographic standards SRP5 and WANG-KE and has cont ...
showed that recursive randomness concept is different from Schnorr's randomness concept.
In most cases, theorems relating the three paradigms (often equivalence) have been proven.
[Wolfgang Merkle, ''Kolmogorov Loveland Stochasticity'' in Automata, languages and programming: 29th international colloquium, ICALP 2002, by Peter Widmayer et al. page 391]
See also
*
Randomness
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...
*
History of randomness
*
Random number generator
Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular out ...
*
Seven states of randomness
The seven states of randomness in probability theory, fractals and risk analysis are extensions of the concept of randomness as modeled by the normal distribution. These seven states were first introduced by Benoît Mandelbrot in his 1997 boo ...
*
Statistical randomness A 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.
Statistical randomness does ...
References
* Sergio B. Volcha
''What Is a Random Sequence?''''The American Mathematical Monthly'', Vol. 109, 2002, pp. 46–63
Notes
External links
*
Videoon frequency stability. Why humans can't "guess" randomly
Randomness tests by Terry Ritter
{{DEFAULTSORT:Random Sequence
Sequences and series
Statistical randomness