No-randomness-from-nothing for computable randomness

I recently added the short article “No-randomness-from-nothing for computable randomness” to the 2014 PDF Logic Blog.

There are two important properties that one would like a notion of algorithmic randomness to have.  The first is called randomness preservation.  It says that if $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is a computable measure-preserving map and $X \in \{0,1\}^\mathbb{N}$ is random, then so is $T(X)$.  While this property holds for most randomness notions—Kurtz randomness, Schnorr randomness, Martin-Löf randomness, weak $n$-randomness, difference randomness, Demuth randomness, Oberwolfach randomness, and $n$-randomness—it fails for computable randomness. (Nonetheless, I have work in preparation—extending previous work—showing that randomness preservation for computable randomness holds for all “naturally occurring” computable measure-preserving maps, but this is not the purpose of this article.)

The purpose of this article to show that the dual property, no-randomness-from-nothing, holds for computable randomness.

Theorem (No-randomness-from-nothing for computable randomness).  Assume $\mu$ is a computable measure and $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is an a.e. computable measure-preserving map.  If $Y \in \{0,1\}^\mathbb{N}$ is computably random, then there is some $X \in \{0,1\}^\mathbb{N}$ such that $T(X)=Y$.

(The proof can be found in the PDF Logic Blog.)

It is previously known that no-randomness-from-nothing holds for Martin-Löf randomness, weak $n$-randomness ($n\geq2$), and $n$-randomness.  This theorem answers a question of Bienvenu and Porter, who asked if it is true for Schnorr and computable randomness. The Schnorr randomness case still remains open.

Open question.  Does no-randomness-from-nothing hold for Schnorr randomness?

(Although, once again, I have work in preparation showing that no-randomness-from-nothing for Schnorr randomness holds for all “naturally occurring” computable measure-preserving maps.)

Leave a Reply