Layerwise computability and image randomness

DOI10.1007/S00224-017-9791-8MaRDI QIDQ1694009zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Laurent Bienvenu, Mathieu Hoyrup, A. Shen

Publication date 1 February 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic randomnessimage randomnesslayerwise computabilityrandom closed setsrandomness deficiency

Mathematics Subject Classification ID

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

Abstract: Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to image distribution if and only if it has a random preimage. This result (for computable distributions and mappings, and Martin-L"of randomness) was known for a long time (folklore); in this paper we prove its natural generalization for layerwise computable mappings, and discuss the related quantitative results.

Review text

Any reasonable notion of randomness should obey the property that the image \(F(x)\) of an object \(x\) is random with respect to the image distribution \(F(P)\) if and only if it has a \(P\)-random \(F\)-preimage. For computable distributions \(P\) and mappings \(F\) and Martin-Löf randomness this result is known for a long time; for layerwise computable mappings it was mentioned in [the second author and \textit{C. Rojas}, Lect. Notes Comput. Sci. 5555, 549--561 (2009; Zbl 1248.03066)]. The paper provides a proof of this result and discusses quantitative results on randomness deficiency and an application to random closed sets and many-valued mappings. To this end in Section 2 some results on layerwise computability are derived. Section 3 discusses image randomness, and the last section contains a quantitative version of the theorem on image randomness from Section 3, a quantitative version for expectation-bounded deficiency, an application to random closed sets and considerations about non-deterministic mappings.

Recommendations

• The interplay of classes of algorithmically random objects
• Algorithmic randomness of continuous functions
• When does randomness come from randomness?
• Random Continuous Functions
• An application of Martin-Löf randomness to effective probability theory

Cites work

• Algorithmic randomness and monotone complexity on product space
• Algorithmic Randomness of Closed Sets
• Algorithmic tests and randomness with respect to a class of measures
• An application of Martin-Löf randomness to effective probability theory
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Energy randomness
• scientific article; zbMATH DE number 472936 (Why is no real title available?)
• Martin-Löf randomness and Galton-Watson processes
• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• Probabilistic Recursive Functions
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences

Cited in

(5)

• Schnorr randomness for noncomputable measures
• How complex is a random picture?
• The Kučera-Gács theorem revisited by Levin
• Permutations of the integers induce only the trivial automorphism of the Turing degrees
• The Intersection of Algorithmically Random Closed Sets and Effective Dimension

This page was built for publication: Layerwise computability and image randomness

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