Randomness deficiencies

DOI10.1007/978-3-319-58741-7_32zbMATH Open1496.03170arXiv1608.08246OpenAlexW4243859886MaRDI QIDQ2011673FDOQ2011673

Authors: Gleb Novikov 

Publication date: 4 August 2017

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Probability with Martingales
• Process complexity and effective random tests
• The definition of random sequences
• Algorithmic tests and randomness with respect to a class of measures
• Exact Expressions for Some Randomness Tests
• Title not available (Why is that?)
• Kolmogorov Complexity and Algorithmic Randomness

Cited In (6)

• Title not available (Why is that?)
• On the role of the law of large numbers in the theory of randomness
• Title not available (Why is that?)
• 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)