# Solovay Randomness

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}$)

-
Sorry I am trying to learn a bit more math. What is the importance of solovay randomness or ML randomness? – Seyhmus Güngören Aug 13 '12 at 19:57
@SeyhmusGüngören Their importance comes from the fact that they are both equivalent to Kolmogorov Randomness and Randomness via effective martingales (sometimes called intrinsic complexity) which are important measures of randomness of binary strings. See this wikipedia article: en.wikipedia.org/wiki/Algorithmically_random_sequence – Francis Adams Aug 13 '12 at 23:57
Thank you very much. I read it. It is related to the randomness in terms of computational complexity. – Seyhmus Güngören Aug 14 '12 at 8:15

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}]\}$.

-

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.

-