2
$\begingroup$

Say that an $x\in 2^{\omega}$ is Solovay random if for all computably enumerable collections of intervals $\{I_n\}$ such that $\sum_n\mu(I_n)<\infty$, then $x\in I_n$ for at most finitely many $n$.

Also say an $x\in 2^{\omega}$ is Martin-Lof random if for all computable collections $\{U_n\}$ of c.e. open sets with $\mu(U_n)\leq2^{-n}$ (these are called Martin-Lof tests) then $x\notin\bigcap_nU_n$ (this is called passing the ML-test). So $x$ is ML-random if it passes all ML-tests.

I'm trying to show that Solovay Randomness is equivalent to ML Randomness. I've thought about each direction but am not able to finish either off.

For one direction, suppose $x$ is Solovay Random and $\{U_n\}$ is a ML-test. We know each $U_n=\bigcup I_{n,m}$, $\{I_{n,m}\}$ is a c.e. collection of intervals, and $x\notin\bigcap I_k$ since $x$ is Solovay random. But that doesn't get us that $x\notin\bigcap U_n$

For the other way suppose $x$ isn't Solovay Random; so there a c.e. collection of intervals $\{I_n\}$ such that $\sum\mu(I_n)<\infty$ but $x\in I_n$ for infinitely many $n$. I want to use these to get a ML-test that is failed by $x$. But I need to be able to computably get a collection of open sets so $x$ is in all of them (so just taking the $I_n$ that include $x$ doesn't work) and I need to computably thin them out to get the measures small enough (the $\mu(I_n)\rightarrow 0$, so that helps, but I need the open sets I end up with to have measure $\leq 2^{-n}$)

  • 0
    Thank you very much. I read it. It is related to the randomness in terms of com$p$utational com$p$lexity.2012-08-14

2 Answers 2

1

Hints:

For the "one direction", you're not using the full strength of $x$'s Solovay randomness.

For the "other way" you can assume $\sum \mu(I_n) \leq 1$. Now consider $U_k := \{x: \exists n_1, \ldots, n_k [ x \in \bigcap_{j=1}^{k}I_{n_j}]\}$.

1

For the definition of a Solovay test, instead of intervals, you can define the test as a uniformly c.e. sequence of open sets $(S_i)$ such that $\sum_{i < \omega} \mu(S_i) < \infty$.

Suppose $X$ is not ML-random. Then there exists a ML-test $(U_n)_{n \in \omega}$ such that $X \in \bigcap_n U_n$. Every ML-test is a Solovay test (use geometric series). So $X$ fails the Solovay test $(U_n)_{n \in \omega}$ since $X$ is in all $U_n$.

Now suppose that $X$ is not Solovay Random. Then there exists a Solovay Test $S_i$ such that $X$ is in infinitely many $S_i$. Since $\sum \mu(S_i) < \infty$, you may assume (by leaving out finitely many) that $\sum \mu(S_i) \leq 1$. Define $U_i$ be the open set

$[|\{\sigma : [\sigma]\subset S_n \text{ for at least } 2^i \text{ many n's }\}|]$

The claim is that $U_n$ is a ML-test. Let $(\sigma_k)$ be a prefix free set such that $[|(\sigma_k)|] = U_n$. Then

$1 \geq \sum \mu (S_i) \geq \sum_{i}\sum_k \mu(S_i \cap [\sigma_k]) \geq 2^n \sum_k 2^{-|\sigma_k|}\leq 2^n \mu(U_n)$

so $\mu(U_n) \leq 2^{-n}$. Since $X$ is in infinitely many of the $S_i$, by definition of that $U_i$, $X \in U_i$ for all $i$. Hence $X \in \bigcap_i U_i$. So $(U_i)$ is a ML-test that $X$ fails. $X$ is not ML-random.