Layerwise computability and image randomness (Q1694009)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Layerwise computability and image randomness |
scientific article |
Statements
Layerwise computability and image randomness (English)
0 references
1 February 2018
0 references
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.
0 references
algorithmic randomness
0 references
layerwise computability
0 references
image randomness
0 references
randomness deficiency
0 references
random closed sets
0 references
0 references