Markov odometer

Dyadic odometer ${\displaystyle T}$ visualized as an interval exchange transformation with the mapping ${\displaystyle (x_{1},x_{2},\cdots )\mapsto \sum _{n=1}^{\infty }{\frac {x_{n}}{2^{n}}}.}$

Dyadic odometer iterated twice; that is ${\displaystyle T^{2}.}$

Dyadic odometer thrice iterated; that is ${\displaystyle T^{3}.}$

Dyadic odometer iterated four times; that is ${\displaystyle T^{4}.}$

The set of all infinite strings in strings in two symbols ${\displaystyle \Omega =\{0,1\}^{\mathbb {N} }}$ has a natural topology, the product topology, generated by the cylinder sets. The product topology extends to a Borel sigma-algebra; let ${\displaystyle {\mathcal {B}}}$ denote that algebra. Individual points ${\displaystyle x\in \Omega }$ are denoted as ${\displaystyle x=(x_{1},x_{2},x_{3},\cdots ).}$

The Bernoulli process is conventionally endowed with a collection of measures, the Bernnoulli measures, given by ${\displaystyle \mu _{p}(x_{n}=1)=p}$ and ${\displaystyle \mu _{p}(x_{n}=0)=1-p}$, for some ${\displaystyle 0<p<1}$ independent of ${\displaystyle n}$. The value of ${\displaystyle p=1/2}$ is rather special; it corresponds to the special case of the Haar measure, when ${\displaystyle \Omega }$ is viewed as a compact Abelian group. Note that the Bernoulli measure is not the same as the 2-adic measure on the dyadic integers! Formally, one can observe that ${\displaystyle \Omega }$ is also the base space for the dyadic integers; however, the dyadic integers are endowed with a metric, the p-adic metric, which induces a metric topology distinct from the product topology used here.

The space ${\displaystyle \Omega }$ can be endowed with addition, defined as coordinate addition, with a carry bit. That is, for each coordinate, let ${\displaystyle (x+y)_{n}=x_{n}+y_{n}+\varepsilon _{n}\,{\bmod {\,}}2}$ where ${\displaystyle \varepsilon _{0}=0}$ and

${\displaystyle \varepsilon _{n}={\begin{cases}0&x_{n-1}+y_{n-1}<2\\1&x_{n-1}+y_{n-1}=2\end{cases}}}$

inductively. Increment-by-one is then called the (dyadic) odometer. It is the transformation ${\displaystyle T:\Omega \to \Omega }$ given by ${\displaystyle T(x)=x+{\underline {1}}}$, where ${\displaystyle {\underline {1}}:=(1,0,0,\dots )}$. It is called the odometer due to how it looks when it "rolls over": ${\displaystyle T}$ is the transformation ${\displaystyle T\left(1,\dots ,1,0,x_{k+1},x_{k+2},\dots \right)=\left(0,\dots ,0,1,x_{k+1},x_{k+2},\dots \right)}$. Note that ${\displaystyle T^{-1}(0,0,\cdots )=(1,1,\cdots )}$ and that ${\displaystyle T}$ is ${\displaystyle {\mathcal {B}}}$-measurable, that is, ${\displaystyle T^{-1}(\sigma )\in {\mathcal {B}}}$ for all ${\displaystyle \sigma \in {\mathcal {B}}.}$

The transformation ${\displaystyle T}$ is non-singular for every ${\displaystyle \mu _{p}}$. Recall that a measurable transformation ${\displaystyle \tau$ :\Omega \to \Omega } is non-singular when, given ${\displaystyle \sigma \in {\mathcal {B}}}$, one has that ${\displaystyle \mu (\tau ^{-1}\sigma )=0}$ if and only if ${\displaystyle \mu (\sigma )=0}$. In this case, one finds

${\displaystyle {\frac {d\mu _{p}\circ T}{d\mu _{p}}}=\left({\frac {1-p}{p}}\right)^{\varphi }}$

where ${\displaystyle \varphi (x)=\min \left\{n\in \mathbb {N} \mid x_{n}=0\right\}-2}$. Hence ${\displaystyle T}$ is nonsingular with respect to ${\displaystyle \mu _{p}}$.

The transformation ${\displaystyle T}$ is ergodic. This follows because, for every ${\displaystyle x\in \Omega }$ and natural number ${\displaystyle n}$, the orbit of ${\displaystyle x}$ under ${\displaystyle T^{0},T^{1},\cdots ,T^{2^{n}-1}}$ is the set ${\displaystyle \{0,1\}^{n}}$. This in turn implies that ${\displaystyle T}$ is conservative, since every invertible ergodic nonsingular transformation in a nonatomic space is conservative.

Note that for the special case of ${\displaystyle p=1/2}$, that ${\displaystyle \left(\Omega ,{\mathcal {B}},\mu _{1/2},T\right)}$ is a measure-preserving dynamical system.

The same construction enables to define such a system for every product of discrete spaces. In general, one writes

${\displaystyle \Omega =\prod _{n\in \mathbb {N} }A_{n}}$

for ${\displaystyle A_{n}=\mathbb {Z} /m_{n}\mathbb {Z} =\{0,1,\dots ,m_{n}-1\}}$ with ${\displaystyle m_{n}\geq 2}$ an integer. The product topology extends naturally to the product Borel sigma-algebra ${\displaystyle {\mathcal {B}}}$ on ${\displaystyle \Omega }$. A product measure on ${\displaystyle {\mathcal {B}}}$ is conventionally defined as ${\displaystyle \textstyle \mu =\prod _{n\in \mathbb {N} }\mu _{n},}$ given some measure ${\displaystyle \mu _{n}}$ on ${\displaystyle A_{n}}$. The corresponding map is defined by

${\displaystyle T(x_{1},\dots ,x_{k},x_{k+1},x_{k+2},\dots )=(0,\dots ,0,x_{k}+1,x_{k+1},x_{k+2},\dots )}$

where ${\displaystyle k}$ is the smallest index for which ${\displaystyle x_{k}\neq m_{k}-1}$. This is again a topological group.

A special case of this is the Ornstein odometer, which is defined on the space

${\displaystyle \Omega =\left(\mathbb {Z} /2\mathbb {Z} \right)\times \left(\mathbb {Z} /3\mathbb {Z} \right)\times \left(\mathbb {Z} /4\mathbb {Z} \right)\times \cdots }$

with the measure a product of

${\displaystyle \mu _{n}(j)={\begin{cases}1/2&{\mbox{ if }}j=0\\1/2(n+1)&{\mbox{ if }}j\neq 0\\\end{cases}}}$