Impossibility of a gambling system
Encyclopedia
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. Although the concept had been vaguely discussed in various forms for some time, it is generally attributed to Richard von Mises, who used the term collective rather than sequence.
Intuitively speaking, the principle states that it is not possible to select a sub-sequence of a random sequence
in a way to improve the odds for a specific event. For instance, if a coin toss sequence is random with equal and independent 50/50 chances for heads and tails, then betting on heads every 3rd, 7th, or 21st toss, etc. does not change the odds of winning in the long run. Richard von Mises likened the principle of the impossibility of a gambling system to the principle of the conservation of energy
, a law that can not be proven, but has held true in repeated experiments.
Elsewhere von Mises had also discussed impossibility of other issues in science and human understanding, e.g. in his book on Positivism
he discussed the impossibility of exact descriptions due to linguistic constraints. And von Mises was also supportive of the notion of the impossibility of strict determinism in physics.
As a framework for the impossibility of a gambling system, Richard von Mises defined an infinite sequence of zeros and ones as a random sequence
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.
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.
The principle influenced modern concepts in randomness, e.g. the work by A. N. Kolmogorov in considering a finite sequence random (with respect to a class of computing systems) if any program that can generate the sequence is at least as long as the sequence itself.
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
. It states that in a random sequence, the selection of sub-sequences does not change the probability of specific elements. Although the concept had been vaguely discussed in various forms for some time, it is generally attributed to Richard von Mises, who used the term collective rather than sequence.
Intuitively speaking, the principle states that it is not possible to select a sub-sequence of a random sequence
Random sequence
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 variables and many statistical discussions begin with the words "let X1,...,Xn be independent random variables...". Yet as D. H. Lehmer stated in...
in a way to improve the odds for a specific event. For instance, if a coin toss sequence is random with equal and independent 50/50 chances for heads and tails, then betting on heads every 3rd, 7th, or 21st toss, etc. does not change the odds of winning in the long run. Richard von Mises likened the principle of the impossibility of a gambling system to the principle of the conservation of energy
Conservation of energy
The nineteenth century law of conservation of energy is a law of physics. It states that the total amount of energy in an isolated system remains constant over time. The total energy is said to be conserved over time...
, a law that can not be proven, but has held true in repeated experiments.
Elsewhere von Mises had also discussed impossibility of other issues in science and human understanding, e.g. in his book on Positivism
Positivism
Positivism is a a view of scientific methods and a philosophical approach, theory, or system based on the view that, in the social as well as natural sciences, sensory experiences and their logical and mathematical treatment are together the exclusive source of all worthwhile information....
he discussed the impossibility of exact descriptions due to linguistic constraints. And von Mises was also supportive of the notion of the impossibility of strict determinism in physics.
As a framework for the impossibility of a gambling system, Richard von Mises defined an infinite sequence of zeros and ones as a random sequence
Random sequence
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 variables and many statistical discussions begin with the words "let X1,...,Xn be independent random variables...". Yet as D. H. Lehmer stated in...
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.
In the mid 1960s, A. N. Kolmogorov
Andrey Kolmogorov
Andrey Nikolaevich Kolmogorov was a Soviet mathematician, preeminent in the 20th century, who advanced various scientific fields, among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity.-Early life:Kolmogorov was born at Tambov...
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.
The principle influenced modern concepts in randomness, e.g. the work by A. N. Kolmogorov in considering a finite sequence random (with respect to a class of computing systems) if any program that can generate the sequence is at least as long as the sequence itself.