6
$\begingroup$

Take an arbitrary infinite binary sequence $\omega$. The interesting case is when $\omega$ is not computable. Is there a computable (semi-)measure $\mu$ such that sequence $\omega$ is $\mu$-random in the sense of Martin-Löf?

Or $\mu$-random is some weaker sense?

Clearly, $\omega$ is $\mu$-random for $\mu$-almost all sequences. So the question is what happens with the sequences from that set of measure zero.

$\endgroup$
  • $\begingroup$ I think it should be easy to build uncomputable sequences which are not random (in any reasonable notion of randomness), e.g. take any uncomputable function $f$, consider the sequence which is 0 on all $n$ expect when $n=2^m$ in which case it is $f(m)$. Clearly this is not computable, but it shouldn't be random in any reasonable notion of randomness. $\endgroup$ – Kaveh Aug 19 '13 at 21:51
  • $\begingroup$ @Kaveh, but might there exist a $\mu$ for which it is $\mu$-random? I am thinking of $\mu$ uniform on all sequences $\omega$ such that $n \neq 2^m \implies \omega_n = 0$, i.e. $\omega$ is zero on all indices that are not powers of two, and either zero or one on indices that are. $\endgroup$ – usul Aug 19 '13 at 23:29
  • $\begingroup$ @usul, I agree, this example will follow from the initial question. And by Jason Rute's argument below, there is an $f$ that would fail randomness $\endgroup$ – Gleb Aug 20 '13 at 15:45
10
$\begingroup$

Mucknik, Semenov and Uspensky showed that there are sequences which are not Martin-Löf random for any computable measure. They call all other sequences (which are Martin-Löf random for some computable measure) "natural sequences".

Andrei A. Muchnik, Alexei Semenov, and Vladimir Uspensky. Mathematical metaphysics of randomness. Theoretical Computer Science, 207(2):263–317, 1998.

This topic is also discussed in

Laurent Bienvenu and Christopher Porter. Effective randomness, strong reductions and Demuth’s theorem.

Jan Reimann and Theodore A. Slaman. Probability measures and effective randomness.

Jan Reimann and Theodore A. Slaman. Measures and their random reals.

Here is a quick proof (which may be different from the above references):

Let $\{U_i\}$ be a (non-effective) enumeration of all $\Sigma^0_1$ sets making up some level of the universal Martin-Löf test for some computable measure $\mu$. Each $U_i$ is dense and open, so by the Baire category theorem (countable intersection of dense open sets is dense), the intersection $\bigcap_i U_i$ is nonempty. Any sequence in this intersection cannot be Martin-Löf random for any computable measure $\mu$.

The same can be done for Schnorr randomness (which is weaker than Martin-Löf randomness). Let $\{U_i\}$ be the collection of all dense $\Sigma^0_1$ sets of computable $\mu$-measure for some computable measure $\mu$.

UPDATE Oct 23, 2013:

I realize there are three things to add (which I am sure are all well-known and they are probably in the above mentioned papers).

  1. My above proof actually shows that 1-generics cannot be Martin-Löf random for a computable measure, since 1-generics are in all dense $\Sigma^0_1$ sets.

  2. The K-trivials are not Martin-Löf random on any computable measure. A sequence $X \in \{0,1\}^\mathbb{N}$ is low-for-random (a.k.a. $K$-trivial) if $\text{MLR}^X = \text{MLR}$. It can be shown that this property also extends to all computable $\mu$. That is, if $X$ is K-trivial, then $\text{MLR}_{\mu}^X = \text{MLR}_{\mu}$ for all computable $\mu$. Hence, the non-computable $K$-trivials cannot be random for any computable measure. For if a $K$-trivial $X$ is random on a computable measure $\mu$ then $X$ is random relative to $X$. This means $X$ is an atom. However, only computable points can be atoms of computable measures.

  3. The set of all "natural sequences" is precisely the set of sequences truth-table reducible to a Martin-Löf random (on the fair-coin measure). (The main idea is that every computable measure is the push-forward on an a.e. computable map, and the Martin-Löf randoms on the measure $\mu$ are exactly the sequences pushed over to the new measure. The reason this computation is "truth-table" involves using "layerwise computability".)

$\endgroup$
  • 2
    $\begingroup$ I just realized you also asked for semi-measures. It is not yet agreed upon what the correct definition of Martin-Löf randomness for a semimeasure is. (There is a very new definition by Levin. Also Bienvenu et al. have explored a number of possible definitions.) Did you have one in mind? $\endgroup$ – Jason Rute Aug 20 '13 at 0:40
  • $\begingroup$ That is great! I mostly meant measure rather than semimeasure. Do you have a reference to the paper? I would like to explore the related stuff. $\endgroup$ – Gleb Aug 20 '13 at 15:57
  • $\begingroup$ I added the references above (and I was wrong about it being due to Levin). For semimeasures the paper by Levin is called "Enumerable Distributions, Randomness, Dependence" (arxiv.org/abs/1208.2955). In this case there is a universal lowersemicomputable semimeasure for which all points are random. The work by Laurent Bienvenu, Christopher Porter and Paul Shafer is still being written, but there are slides on the web, for example hoelzl.fr/Hoelzl%20-%20Randomness%20for%20semi-measures.pdf $\endgroup$ – Jason Rute Aug 21 '13 at 17:09
  • $\begingroup$ The paper by Laurent Bienvenu, Rupert Hölzl, Christopher Porter and Paul Shafer on randomness for semimeasures just came out: arxiv.org/abs/1310.5133v2. $\endgroup$ – Jason Rute Oct 23 '13 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.