Randomness with respect to a measure

Martin-Löf randomness for arbitrary measures on $2^\omega$:

Definition.
A test for $\mu$-randomness is a uniformly $\Sigma^0_1(\mu)$ sequence $\{U_n\}_{n\in\omega}$ with $\mu(U_n)\le 2^{-n}$.

The test $\{U_n\}_{n\in\mathbb{N}}$ defines a null set $\cap_n U_n$. $X$ passes the test for randomness $\{U_n\}_{n\in\mathbb{N}}$ if $X\not\in \cap_n U_n$. If $X$ passes all $\mu$-randomness tests then $X$ is $\mu$-random.

Bernoulli measures

For each $n\in\omega$,
$$\mu_p(\{X: X(n)=1\})=p$$
$$\mu_p(\{X:X(n)=0\})=1-p$$
and $X(0),X(1),X(2),\ldots$ are mutually independent random variables.

Example.
The Strong Law of Large Numbers for $\mu_p$ states that for almost all $X$ according to the measure $\mu_p$, we have
$$\forall\varepsilon>0\,\exists N\,\forall n>N\, \left| \frac{\text{the $\#$ of 1s up to $n$ in $X$}}{n}-p\right| <\varepsilon.$$
Suppose $X$ does not satisfy the SLLN, as witnessed by a number $\varepsilon_0$. Let
$$U_N=\{Z: \exists n>N \, \left| \frac{\text{the $\#$ of 1s up to $n$ in $X$}}{n}-p\right| \ge \varepsilon_0\}.$$
Then $U_N$ is open and in fact $\Sigma^0_1(\mu_p)$; and $\mu(U_N)$ goes effectively to $0$. Thus, $X$ is not Martin-Löf random with respect to $\mu_p$.

Definition.
A set $Y\subseteq \mathbb{N}$ is feeble if it is infinite, and no Martin-Löf random set is computable from $Y$.

Theorem[Law of Feeble Subsets]
Almost every $X\subseteq\mathbb{N}$, according to $\mu:=\mu_{1/2}$, has a feeble subset $Y\subseteq X$.

(Passing from $X$ to $Y$ we suffer a “loss of randomness beyond algorithmic repair.”)

Example.
Let $X$ be Martin-Löf random and let $Y$ be a computably chosen subset of $X$. Say,
$$Y=\langle X(0),0,X(2),0,X(4),0,\ldots\rangle.$$
Then $Y$ is an infinite subset of $X$, but $Y$ does compute a Martin-Löf random set, namely
$$Z=\langle X(2),X(4),X(6),X(8),\ldots\rangle$$
so $Y$ is not feeble.

Generally, if $X$ is Martin-Löf random and $R$ is computable ($R\le_T\emptyset$) then $X\cap R$ is not feeble.

Question.
If there a Martin-Löf random set $X$ and a set $R\le_T X$ such that $R\cap X$ is feeble?

Partial negative result: such an $X$ can not be hyperimmune-free.

von Neumann’s randomness extractor

Let $X$ be Martin-Löf random let $Y$ be a “randomly chosen” subset of $X$. That, is each 1 in $X$ is converted to a 0 with probability $\frac{1}{2}$. Then $Y$ does compute a Martin-Löf random set. Namely, let $Z$ be obtained from $X$ by making the following replacements:
$$\langle X(2n),X(2n+1)\rangle \mapsto Z(n)$$
$$\langle 0,0\rangle \mapsto \langle \rangle$$
$$\langle 1,1\rangle \mapsto \langle \rangle$$
$$\langle 0,1\rangle \mapsto \langle 0\rangle$$
$$\langle 1,0\rangle \mapsto \langle 1\rangle$$

How dense can a feeble subset $Y\subseteq X$ be?

The principal function of a set $Y$ is given by $p(n)=$ the smallest element of $Y$ that is $>p(n-1)$.

• K., 2007: principal function bounded by $4^n$.
• Miller, 2008: principal function bounded by $n^{2+\varepsilon}$.

Question.
Can a Martin-Löf random set $X$ have a feeble subset $Y$ of linear density, i.e. principal function bounded by $c\cdot n$?

One way to approach this question is to start with stronger reducibilities.

Definition.
Let $r$ be a reducibility. $Y$ is $r$-feeble if $Y$ is infinite and $Y$ does not $r$-compute any ML-random set.

$c$, $d$, and $btt$-feeble subsets of linear density

Take $Y$ to be a $\mu_p$-random subset of $X$. Then $Y$ has principal function bounded by $({p}^{-1}+\varepsilon)n$ ($Y$ has linear density) and $Y$ is $c$-feeble, $d$-feeble, and $btt$-feeble.

However, using von Neumann’s extractor one can show that $Y$ is not $tt$-feeble. By using different algorithms one can show that $Y$ is also not $l$-feeble nor $p$-feeble.

Question.
Is there an $r$-feeble subset of $X$ of linear density, for $r\in\{p,l\}$? Or even for $r\in\{tt,T\}$?

The 7 clones in Post’s lattice containing the constant functions correspond to reducibilities $m$, $btt(1)$, $c$, $d$, $p$, $l$, $tt$ and out of these 7 a $\mu_p$-random set is feeble for exactly 4.

Reducibilities for which a $\mu_p$-random set is feeble:

• $m$: $\{0,1\}$
• $btt(1)$: $\{0,\neg\}$
• $c$: $\{0,1,\wedge\}$ (conjunctive)
• $d$: $\{0,1,\vee\}$ (disjunctive)

and those for which it is not:

• $p$: $\{0,1,\wedge,\vee\}$ (positive)
• $\ell$: $\{0,\iff\}$
• $tt$: $\{\neg,\vee\}$

When is a measure “close enough” to uniform?

Theorem[Kakutani 1948]
Let $\mu$ and $\nu$ be strongly positive (i.e. the $p_i$, $q_i$ are bounded away from $0$ and $1$) generalized Bernoulli measures of parameters $\{p_i\}_{i\in\mathbb{N}}$ and $\{q_i\}_{i\in\mathbb{N}}$, respectively. If $\sum_i (p_i-q_i)^2<\infty$ then $\mu$ and $\nu$ are equivalent (i.e. have the same null sets).

Theorem[Vovk 1987]
Let $\mu$ and $\nu$ be computable strongly positive generalized Bernoulli measures of parameters $\{p_i\}_{i\in\mathbb{N}}$ and $\{q_i\}_{i\in\mathbb{N}}$, respectively. If $\sum_i (p_i-q_i)^2<\infty$ then $\mu$MLR=$\nu$MLR.

Linear reducibility

$Z$ is linearly reducible to $Y$ ($Z\le_\ell Y$) if the truth of the equation $Z(n)=1$ can effectively be reduced to the truth of a linear equation in the variables $Y(0), Y(1), \ldots$ over the finite field $\mathbb Z/2\mathbb Z = (\{0,1\},+)$:

$$Z(43)=1\Leftrightarrow Y(3)+Y(5)=0$$
$$Z(44)=1\Leftrightarrow Y(1)+Y(6)+Y(8)=1$$
$$\ldots$$
One way to state this:

Definition.
$Z\le_{\ell}Y$ if there is a recursive function $f$ such that for all $n$,
$$n\in Z\iff |D_{f(n)}\cap Y|\equiv 1(\text{mod }2).$$

An improved von Neumann extractor (in a sense)

Theorem
A $\mu_p$-random set is not $\ell$-feeble.

Proof.
Suppose $Y$ is $\mu_p$-random. The $\mu_p$-probability that $|D_{f(n)}\cap Y|\equiv 1(\text{mod }2)$ is computable from $p$ and converges effectively to $1/2$ as $|D_{f(n)}|\to\infty$. \footnote{\tiny{The reason is that if $D_{f(n)}$ is very large, then it is likely to contain a large amount of numbers from $Y$, and this amount is about equally likely to be odd or even. }}

Let $D_{f(n)}$ be disjoint finite sets that are so large that if $p_i:=\mu_p(\{Y:|D_{f(i)}\cap Y|\equiv 1(\text{mod }2)\})$ then $\sum_i (p_i-\frac{1}{2})^2<\infty$.

If $Z$ is reduced to $Y$ via $D_{f(n)}$, then $Z$ is ML-random.

Positive reducibility

$Z\le_p Y$ iff there is a recursive function $f$ such that for all $n$, $n\in Z$ iff $\exists i\le k_i$ $D_{f(n,i)}\subseteq Y$.

We can rewrite this:
\begin{equation}(*)
\tag{*}\neg \forall i\le k_i [D_{f(n,i)}\not\subseteq Y]
\end{equation}

If the $D_{f(n,i)}$ are disjoint then the events $[D_{f(n,i)}\not\subseteq Y]$ are independent and so we can calculate the probability of (*).

By taking $|D_{f(n,i)}|$ large enough and taking $k_i$ large enough we can get this probability as close to $1/2$ as desired. Thus,

Theorem[A second improved von Neumann extractor]
Let $0<q<1$. A $\mu_q$-random set is not $p$-feeble.