When does randomness come from randomness?

DOI10.1016/J.TCS.2016.05.001zbMATH Open1339.68127arXiv1508.05082OpenAlexW2962835668MaRDI QIDQ287436FDOQ287436

Publication date: 26 May 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A result of Shen says that if

F c o l o n 2^{m a t h b b N} i g h t a r r o w 2^{m a t h b b N}

is an almost-everywhere computable, measure-preserving transformation, and

y i n 2^{m a t h b b N}

is Martin-L"of random, then there is a Martin-L"of random

x i n 2^{m a t h b b 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^{m a t h b b N}

satisfying this property and also satisfying randomness preservation: if

F c o l o n 2^{m a t h b b N} i g h t a r r o w 2^{m a t h b b N}

is an almost-everywhere computable, measure-preserving map, and if

x i n 2^{m a t h b b N}

is random, then

F (x)

is random.

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

Recommendations

zbMATH Keywords

computable analysis algorithmic randomness Schnorr randomness computable randomness no randomness ex nihilo no randomness from nothing randomness conservation randomness preservation recursive randomness

Mathematics Subject Classification ID

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

Cites Work

Cited In (7)

This page was built for publication: When does randomness come from randomness?

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