SAS

Abstract

For $x=x_1x_2\cdots,y=y_1y_2\cdots\in\{0,1\}^\infty$, let $x^n:=x_1\cdots x_n$ and $x/y:=x_{\tau(1)}x_{\tau(2)}\cdots$ where $\{i\mid y_i=1\}=\{\tau(1)<\tau(2)<\cdots\}$. Our first problem is to identify Martin-Löf randomness of $x$ in terms of randomness of subsequences $x/y$ for some finite set of selection functions $y$. This is trivial if we allow $y=s1^\infty$ for any finite string $s$, where $1^\infty$ is the sequence of 1's. In the following, we say that a selection function is non-trivial if it contains infinitely many 1's and 0's. Let ${\cal R}^P$ be the set of Martin-Löf random sequences w.r.t. a computable probability $P$ on $\{0,1\}^\infty$.

The following two statements are equivalent.

1. $x\in {\cal R}^u$, where $u$ is the uniform measure on $\{0,1\}^\infty$.
2. $\exists \mbox{ computable }w\ \ x\in{\cal R}^w \mbox{ and }x/y_i(w, x)\in{\cal R}^u\mbox{ for }i=1,2,\ldots, 6, \mbox{ where }\\ \{y_1(w, x),\ldots, y_6(w, x )\} \mbox{ consists of non-trivial selection functions and depends on } w\mbox{ and }x.$

The author do not know whether we can drop the assumption that $x$ is random w.r.t. some computable probability in (ii), i.e., whether we can replace (ii) with $x/y\in R^u$ for $y\in Y^x$ where $Y^x$ consists of non-trivial selection functions and depends on $x$. We also have a similar algorithmic analogy for Steinhause theorem [1].

Let $w$ be a computable probability such that

1. $\forall y\in{\cal R}^w,\ \lim_n K(y^n)/n=0$, (b) $\lim_n \sum_{1\leq i\leq n} y_i/n$ exists for $y\in{\cal R}^w$, and
2. $\forall \epsilon >0 \exists y\in{\cal R}^w \lim_n \sum_{1\leq i\leq n} y_i/n>1-\epsilon$.

Then the following two statements are equivalent.

1. $\lim_{n\to\infty} \frac{1}{n}K(x^n)=1$.
2. $\lim_{n\to\infty} \frac{1}{| x^n/y^n|}K(x^n/y^n)=1$ for $y\in{\cal R}^w$, where $K$ is the prefix-complexity.

For example, $w:=\int P_\rho d\rho$, where $P_\rho$ is a probability derived from irrational rotation with parameter $\rho$, satisfies the condition of Prop. 2, see [2]. There are similar algorithmic analogies for Kamae's theorem [4], see [3].

[1] H. Steinhaus. "Les probabilités dénombrables et leur rapport à la théorie de la meésure." Fund. Math., 4:286–310, 1922.

[2] H. Takahashi and K. Aihara. "Algorithmic analysis of irrational rotations in a sigle neuron model." J. Complexity, 19:132–152, 2003.

[3] H. Takahashi. "Algorithmic analogies to Kamae-Weiss theorem on normal numbers." In Solomonoff 85th memorial conference. To appear in LNAI.

[4] T. Kamae. "Subsequences of normal numbers." Israel J. Math., 16:121–149, 1973.