[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/markov-odometer-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki40\/markov-odometer-wikipedia\/","headline":"Markov odometer – Wikipedia","name":"Markov odometer – Wikipedia","description":"before-content-x4 In mathematics, a Markov odometer is a certain type of topological dynamical system. It plays a fundamental role in","datePublished":"2016-07-02","dateModified":"2016-07-02","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki40\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/2dca0637ce4cd40429737faea37bfd944a2ac73d","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/2dca0637ce4cd40429737faea37bfd944a2ac73d","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki40\/markov-odometer-wikipedia\/","about":["Wiki"],"wordCount":16309,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4In mathematics, a Markov odometer is a certain type of topological dynamical system. It plays a fundamental role in ergodic theory and especially in orbit theory of dynamical systems, since a theorem of H. Dye asserts that every ergodic nonsingular transformation is orbit-equivalent to a Markov odometer.[1]       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4The basic example of such system is the “nonsingular odometer”, which is an additive topological group defined on the product space of discrete spaces, induced by addition defined as x\u21a6x+1_{displaystyle xmapsto x+{underline {1}}}, where 1_:=(1,0,0,\u2026){displaystyle {underline {1}}:=(1,0,0,dots )}. This group can be endowed with the structure of a dynamical system; the result is a conservative dynamical system.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4The general form, which is called “Markov odometer”, can be constructed through Bratteli\u2013Vershik diagram to define Bratteli\u2013Vershik compactum space together with a corresponding transformation.Table of ContentsNonsingular odometers[edit]Dyadic odometer[edit]Integer odometers[edit]Sandpile model[edit]Markov odometer[edit]See also[edit]References[edit]Further reading[edit]Nonsingular odometers[edit]Several kinds of non-singular odometers may be defined.[2]These are sometimes referred to as adding machines.[3]The simplest is illustrated with the Bernoulli process. This is the set of all infinite strings in two symbols, here denoted by        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4\u03a9={0,1}N{displaystyle Omega ={0,1}^{mathbb {N} }} endowed with the product topology. This definition extends naturally to a more general odometer defined on the product space\u03a9=\u220fn\u2208N(Z\/knZ){displaystyle Omega =prod _{nin mathbb {N} }left(mathbb {Z} \/k_{n}mathbb {Z} right)}for some sequence of integers (kn){displaystyle (k_{n})} with each kn\u22652.{displaystyle k_{n}geq 2.}The odometer for kn=2{displaystyle k_{n}=2} for all n{displaystyle n} is termed the dyadic odometer, the von Neumann\u2013Kakutani adding machine or the dyadic adding machine.The topological entropy of every adding machine is zero.[3] Any continuous map of an interval with a topological entropy of zero is topologically conjugate to an adding machine, when restricted to its action on the topologically invariant transitive set, with periodic orbits removed.[3]Dyadic odometer[edit]  Dyadic odometer T{displaystyle T} visualized as an interval exchange transformation with the mapping (x1,x2,\u22ef)\u21a6\u2211n=1\u221exn2n.{displaystyle (x_{1},x_{2},cdots )mapsto sum _{n=1}^{infty }{frac {x_{n}}{2^{n}}}.}  Dyadic odometer iterated twice; that is T2.{displaystyle T^{2}.}  Dyadic odometer thrice iterated; that is T3.{displaystyle T^{3}.}  Dyadic odometer iterated four times; that is T4.{displaystyle T^{4}.}The set of all infinite strings in strings in two symbols \u03a9={0,1}N{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 B{displaystyle {mathcal {B}}} denote that algebra. Individual points x\u2208\u03a9{displaystyle xin Omega } are denoted as x=(x1,x2,x3,\u22ef).{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 \u03bcp(xn=1)=p{displaystyle mu _{p}(x_{n}=1)=p} and \u03bcp(xn=0)=1\u2212p{displaystyle mu _{p}(x_{n}=0)=1-p}, for some 0{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 \u03a9{displaystyle Omega } can be endowed with addition, defined as coordinate addition, with a carry bit. That is, for each coordinate, let(x+y)n=xn+yn+\u03b5nmod2{displaystyle (x+y)_{n}=x_{n}+y_{n}+varepsilon _{n},{bmod {,}}2}where \u03b50=0{displaystyle varepsilon _{0}=0} and\u03b5n={0xn\u22121+yn\u221211=2{displaystyle varepsilon _{n}={begin{cases}0&x_{n-1}+y_{n-1}\u03a9{displaystyle T:Omega to Omega } given by T(x)=x+1_{displaystyle T(x)=x+{underline {1}}}, where 1_:=(1,0,0,\u2026){displaystyle {underline {1}}:=(1,0,0,dots )}. It is called the odometer due to how it looks when it “rolls over”: T{displaystyle T} is the transformation T(1,\u2026,1,0,xk+1,xk+2,\u2026)=(0,\u2026,0,1,xk+1,xk+2,\u2026){displaystyle Tleft(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 T\u22121(0,0,\u22ef)=(1,1,\u22ef){displaystyle T^{-1}(0,0,cdots )=(1,1,cdots )} and that T{displaystyle T} is B{displaystyle {mathcal {B}}}-measurable, that is, T\u22121(\u03c3)\u2208B{displaystyle T^{-1}(sigma )in {mathcal {B}}} for all \u03c3\u2208B.{displaystyle sigma in {mathcal {B}}.}The transformation T{displaystyle T} is non-singular for every \u03bcp{displaystyle mu _{p}}. Recall that a measurable transformation \u03c4:\u03a9\u2192\u03a9{displaystyle tau :Omega to Omega } is non-singular when, given \u03c3\u2208B{displaystyle sigma in {mathcal {B}}}, one has that \u03bc(\u03c4\u22121\u03c3)=0{displaystyle mu (tau ^{-1}sigma )=0} if and only if \u03bc(\u03c3)=0{displaystyle mu (sigma )=0}. In this case, one findsd\u03bcp\u2218Td\u03bcp=(1\u2212pp)\u03c6{displaystyle {frac {dmu _{p}circ T}{dmu _{p}}}=left({frac {1-p}{p}}right)^{varphi }}where \u03c6(x)=min{n\u2208N\u2223xn=0}\u22122{displaystyle varphi (x)=min left{nin mathbb {N} mid x_{n}=0right}-2}. Hence T{displaystyle T} is nonsingular with respect to \u03bcp{displaystyle mu _{p}}.The transformation T{displaystyle T} is ergodic. This follows because, for every x\u2208\u03a9{displaystyle xin Omega } and natural number n{displaystyle n}, the orbit of x{displaystyle x} under T0,T1,\u22ef,T2n\u22121{displaystyle T^{0},T^{1},cdots ,T^{2^{n}-1}} is the set {0,1}n{displaystyle {0,1}^{n}}. This in turn implies that T{displaystyle T} is conservative, since every invertible ergodic nonsingular transformation in a nonatomic space is conservative.Note that for the special case of p=1\/2{displaystyle p=1\/2}, that (\u03a9,B,\u03bc1\/2,T){displaystyle left(Omega ,{mathcal {B}},mu _{1\/2},Tright)} is a measure-preserving dynamical system.Integer odometers[edit]The same construction enables to define such a system for every product of discrete spaces.  In general, one writes\u03a9=\u220fn\u2208NAn{displaystyle Omega =prod _{nin mathbb {N} }A_{n}}for An=Z\/mnZ={0,1,\u2026,mn\u22121}{displaystyle A_{n}=mathbb {Z} \/m_{n}mathbb {Z} ={0,1,dots ,m_{n}-1}} with mn\u22652{displaystyle m_{n}geq 2} an integer. The product topology extends naturally to the product Borel sigma-algebra B{displaystyle {mathcal {B}}} on \u03a9{displaystyle Omega }.  A product measure on B{displaystyle {mathcal {B}}} is conventionally defined as \u03bc=\u220fn\u2208N\u03bcn,{displaystyle textstyle mu =prod _{nin mathbb {N} }mu _{n},} given some measure \u03bcn{displaystyle mu _{n}} on An{displaystyle A_{n}}. The corresponding map is defined byT(x1,\u2026,xk,xk+1,xk+2,\u2026)=(0,\u2026,0,xk+1,xk+1,xk+2,\u2026){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 k{displaystyle k} is the smallest index for which xk\u2260mk\u22121{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\u03a9=(Z\/2Z)\u00d7(Z\/3Z)\u00d7(Z\/4Z)\u00d7\u22ef{displaystyle Omega =left(mathbb {Z} \/2mathbb {Z} right)times left(mathbb {Z} \/3mathbb {Z} right)times left(mathbb {Z} \/4mathbb {Z} right)times cdots }with the measure a product of\u03bcn(j)={1\/2\u00a0if\u00a0j=01\/2(n+1)\u00a0if\u00a0j\u22600{displaystyle mu _{n}(j)={begin{cases}1\/2&{mbox{ if }}j=0\\1\/2(n+1)&{mbox{ if }}jneq 0\\end{cases}}}Sandpile model[edit]A concept closely related to the conservative odometer is that of the abelian sandpile model. This model replaces the directed linear sequence of finite groups constructed above by an undirected graph (V,E){displaystyle (V,E)} of vertexes and edges. At each vertex v\u2208V{displaystyle vin V} one places a finite group Z\/nZ{displaystyle mathbb {Z} \/nmathbb {Z} } with n=deg(v){displaystyle n=deg(v)} the degree of the vertex v{displaystyle v}. Transition functions are defined by the graph Laplacian. That is, one can increment any given vertex by one; when incrementing the largest group element (so that it increments back down to zero), each of the neighboring vertexes are incremented by one.Sandpile models differ from the above definition of a conservative odometer in three different ways. First, in general, there is no unique vertex singled out as the starting vertex, whereas in the above, the first vertex is the starting vertex; it is the one that is incremented by the transition function. Next, the sandpile models in general use undirected edges, so that the wrapping of the odometer redistributes in all directions. A third difference is that sandpile models are usually not taken on an infinite graph, and that rather, there is one special vertex singled out, the “sink”, which absorbs all increments and never wraps. The sink is equivalent to cutting away the infinite parts of an infinite graph, and replacing them by the sink; alternately, as ignoring all changes past that termination point.Markov odometer[edit]Let B=(V,E){displaystyle B=(V,E)} be an ordered Bratteli\u2013Vershik diagram, consists on a set of vertices of the form \u2210n\u2208NV(n){displaystyle textstyle coprod _{nin mathbb {N} }V^{(n)}} (disjoint union) where V0{displaystyle V^{0}} is a singleton and on a set of edges \u2210n\u2208NE(n){displaystyle textstyle coprod _{nin mathbb {N} }E^{(n)}} (disjoint union).The diagram includes source surjection-mappings sn:E(n)\u2192V(n\u22121){displaystyle s_{n}:E^{(n)}to V^{(n-1)}} and range surjection-mappings rn:E(n)\u2192V(n){displaystyle r_{n}:E^{(n)}to V^{(n)}}. We assume that e,e\u2032\u2208E(n){displaystyle e,e’in E^{(n)}} are comparable if and only if rn(e)=rn(e\u2032){displaystyle r_{n}(e)=r_{n}(e’)}.For such diagram we look at the product space E:=\u220fn\u2208NE(n){displaystyle textstyle E:=prod _{nin mathbb {N} }E^{(n)}} equipped with the product topology. Define “Bratteli\u2013Vershik compactum” to be the subspace of infinite paths,XB:={x=(xn)n\u2208N\u2208E\u2223xn\u2208E(n)\u00a0and\u00a0r(xn)=s(xn+1)}{displaystyle X_{B}:=left{x=(x_{n})_{nin mathbb {N} }in Emid x_{n}in E^{(n)}{text{ and }}r(x_{n})=s(x_{n+1})right}}Assume there exists only one infinite path xmax=(xn)n\u2208N{displaystyle x_{max }=(x_{n})_{nin mathbb {N} }} for which each xn{displaystyle x_{n}} is maximal and similarly one infinite path xmin{displaystyle x_{text{min}}}. Define the “Bratteli-Vershik map” TB:XB\u2192XB{displaystyle T_{B}:X_{B}to X_{B}} by T(xmax)=xmin{displaystyle T(x_{max })=x_{min }} and, for any x=(xn)n\u2208N\u2260xmax{displaystyle x=(x_{n})_{nin mathbb {N} }neq x_{max }} define TB(x1,\u2026,xk,xk+1,\u2026)=(y1,\u2026,yk,xk+1,\u2026){displaystyle T_{B}(x_{1},dots ,x_{k},x_{k+1},dots )=(y_{1},dots ,y_{k},x_{k+1},dots )}, where k{displaystyle k} is the first index for which xk{displaystyle x_{k}} is not maximal and accordingly let (y1,\u2026,yk){displaystyle (y_{1},dots ,y_{k})} be the unique path for which y1,\u2026,yk\u22121{displaystyle y_{1},dots ,y_{k-1}} are all maximal and yk{displaystyle y_{k}} is the successor of xk{displaystyle x_{k}}. Then TB{displaystyle T_{B}} is homeomorphism of XB{displaystyle X_{B}}.Let P=(P(1),P(2),\u2026){displaystyle P=left(P^{(1)},P^{(2)},dots right)} be a sequence of stochastic matrices P(n)=(p(v,e)\u2208Vn\u22121\u00d7E(n)(n)){displaystyle P^{(n)}=left(p_{(v,e)in V^{n-1}times E^{(}n)}^{(n)}right)} such that 0}”\/> if and only if v=sn(e){displaystyle v=s_{n}(e)}. Define “Markov measure” on the cylinders of XB{displaystyle X_{B}} by \u03bcP([e1,\u2026,en])=ps1(e1),e1(1)\u22efpsn(en),en(n){displaystyle mu _{P}([e_{1},dots ,e_{n}])=p_{s_{1}(e_{1}),e_{1}}^{(1)}cdots p_{s_{n}(e_{n}),e_{n}}^{(n)}}. Then the system (XB,B,\u03bcP,TB){displaystyle left(X_{B},{mathcal {B}},mu _{P},T_{B}right)} is called a “Markov odometer”.One can show that the nonsingular odometer is a Markov odometer where all the V(n){displaystyle V^{(n)}} are singletons.See also[edit]References[edit]Further reading[edit]Aaronson, J. (1997). An Introduction to Infinite Ergodic Theory. Mathematical surveys and monographs. Vol.\u00a050. American Mathematical Society. pp.\u00a025\u201332. ISBN\u00a09781470412814.Dooley, Anthony H. (2003). “Markov odometers”.  In Bezuglyi, Sergey; Kolyada, Sergiy (eds.). Topics in dynamics and ergodic theory. Survey papers and mini-courses presented at the international conference and US-Ukrainian workshop on dynamical systems and ergodic theory, Katsiveli, Ukraine, August 21\u201330, 2000. Lond. Math. Soc. Lect. Note Ser. Vol.\u00a0310. Cambridge: Cambridge University Press. pp.\u00a060\u201380. ISBN\u00a00-521-53365-1. Zbl\u00a01063.37005.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/markov-odometer-wikipedia\/#breadcrumbitem","name":"Markov odometer – Wikipedia"}}]}]