Randomness deficiencies

DOI10.1007/978-3-319-58741-7_32MaRDI QIDQ2011673zbMATH OpenOpenAlexFDO

Authors Gleb Novikov

Publication date 4 August 2017

Full work available at URL https://arxiv.org/abs/1608.08246

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: The notion of random sequence was introduced by Martin-Loef in 1966. At the same time he defined the so-called randomness deficiency function that shows how close are random sequences to non-random (in some natural sense). Other deficiency functions can be obtained from the Levin-Schnorr theorem, that describes randomness in terms of Kolmogorov complexity. The difference between all of these deficiencies is bounded by a logarithmic term. In this paper we show that the difference between some deficiencies can be as large as possible.

Recommendations

• On the role of the law of large numbers in the theory of randomness
• Statistical properties of finite sequences with high Kolmogorov complexity
• Kolmogorov-Loveland stochasticity for finite strings
• scientific article; zbMATH DE number 4119313
• Non-approximability of the Randomness Deficiency Function

Cites work

• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• Algorithmic tests and randomness with respect to a class of measures
• Exact Expressions for Some Randomness Tests
• Kolmogorov Complexity and Algorithmic Randomness
• Probability with Martingales
• Process complexity and effective random tests
• The definition of random sequences

Cited in

(6)

• scientific article; zbMATH DE number 4176096 (Why is no real title available?)
• On the role of the law of large numbers in the theory of randomness
• scientific article; zbMATH DE number 4041257 (Why is no real title available?)
• Randomness is inherently imprecise
• Randomness Tests: Theory and Practice
• Non-approximability of the Randomness Deficiency Function

This page was built for publication: Randomness deficiencies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011673)