Use this tag for questions related to algorithmic randomness, which is the study of random individual elements in sample spaces.
Algorithmic randomness is the study of random individual elements in sample spaces, mostly the set of all infinite binary sequences. An algorithmically random element passes all effectively devised tests for randomness.
The theory of algorithmic randomness tries to clarify what it means for an individual element of a sample space, such as a sequence of coin tosses represented as a binary string, to be random. While Kolmogorov's formalization of classical probability theory assigns probabilities to sets of outcomes and determines how to calculate with such probabilities, it does not distinguish between individual random and non-random elements. For example, under a uniform distribution, the outcome "000000000000000...0" (n zeros) has the same probability as any other outcome of n coin tosses, namely 2$^{-n}.$ However, there is an intuitive feeling that a sequence of all zeros is not very random. This is even more so when looking at infinite sequences. It seems desirable to clarify what we mean when we speak of a random object. The modern view of algorithmic randomness proposes three paradigms to distinguish random from non-random elements:
- Unpredictability: It should be impossible to win against a random sequence in a fair betting game when using a feasible betting strategy.
- Incompressibility: It should be impossible to feasibly compress a random sequence.
- Measure theoretical typicalness: Random sequences pass every feasible statistical test.
It is the characteristic feature of algorithmic randomness that it interprets feasible as algorithmically feasible.
