pith. sign in

arxiv: 1508.05082 · v2 · pith:OMB5Q7Z3new · submitted 2015-08-20 · 🧮 math.LO

When does randomness come from randomness?

classification 🧮 math.LO
keywords mathbbrandomnessrandomcomputablemartin-lalmost-everywherecolon2measure-preserving
0
0 comments X
read the original abstract

A result of Shen says that if $F\colon2^{\mathbb{N}}\rightarrow2^{\mathbb{N}}$ is an almost-everywhere computable, measure-preserving transformation, and $y\in2^{\mathbb{N}}$ is Martin-L\"of random, then there is a Martin-L\"of random $x\in2^{\mathbb{N}}$ such that $F(x)=y$. Answering a question of Bienvenu and Porter, we show that this property holds for computable randomness, but not Schnorr randomness. These results, combined with other known results, imply that the set of Martin-L\"of randoms is the largest subset of $2^{\mathbb{N}}$ satisfying this property and also satisfying randomness preservation: if $F\colon2^{\mathbb{N}}\rightarrow2^{\mathbb{N}}$ is an almost-everywhere computable, measure-preserving map, and if $x\in2^{\mathbb{N}}$ is random, then $F(x)$ is random.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.