The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Algorithmic randomness and stochastic selection function

Takahashi, H (University of Electro-Communications, Tokyo)
Friday 06 July 2012, 12:00-12:30

Seminar Room 1, Newton Institute


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.


[pdf ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧