skip to content

Algorithmic randomness and stochastic selection function

Friday 6th July 2012 - 12:00 to 12:30
INI Seminar Room 1
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) 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.

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.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons