Algorithmic tests and randomness with respect to a class of measures
- 16 October 2011
- journal article
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 274 (1) , 34-89
Abstract
This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B p have the important property that p can be recovered from each random sequence of B p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Randomness for non-computable measuresTransactions of the American Mathematical Society, 2013
- Local stability of ergodic averagesTransactions of the American Mathematical Society, 2009
- Computability of probability measures and Martin-Löf randomness over metric spacesInformation and Computation, 2009
- An Application of Martin-Löf Randomness to Effective Probability Theory2009
- On-Line Probability, Complexity and Randomness2008
- Uniform test of algorithmic randomness over a general spaceTheoretical Computer Science, 2005
- On the relation between descriptional complexity and algorithmic probabilityTheoretical Computer Science, 1983
- Exact Expressions for Some Randomness TestsMathematical Logic Quarterly, 1980
- A Theory of Program Size Formally Identical to Information TheoryJournal of the ACM, 1975
- Logical basis for information theory and probability theoryIEEE Transactions on Information Theory, 1968