Fundamental Markov systems

《Fundamental Markov systems》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

Fundamentalarkovsystems
vanWerneros ow,RussiaEmail:ivan_wernermail.ruFebruary9,2009Abstra tWe ontinuedevelopmentofthetheoryofarkovsystemsinitiatedin[34℄.
nthispaper,weintrodu efundamentalarkovsystemsasso iatedwithrandomdynami alsystemsandshowthattheproofoftheunique-nessandempiri alnessofthestationaryinitialdistributionoftherandomdynami alsystemredu estothatforthefundamentalarkovsystemasso iatedwithit.Thestability riteriaforthelatteraremu h learer.SC:6005,37A50,37H99,28A80eywords:arkovsystems,randomdynami alsystems,iteratedfun -tionsystemswithpla e-dependentprobabilities,randomsystemswith omplete onne tions,g-measures,arkovhains,fra tals.
n[34℄,theauthorinitiatedthestudyofageneral on eptofaarkovsystem.Thiswasmotivatedbyadesiretohaveas ienti ally onsistentunifyingmath-emati alstru turewhi hwould overnitearkov hains[10℄,g-measures[25℄anditeratedfun tionsystemswithpla e-dependentprobabilities[1℄,[13℄.Thepurposeofthisnoteistoshowthatthestru tureofaarkovsystemarisesnaturally(possiblyunavoidably)inthestudyofrandomdynami alsystems.1Randomdynami alsystemsarXiv:math/0509120v7[math.PR]9Feb2009et(K,d)bea ompleteseparablemetri spa eandEa ountableset.Forea he∈EletaBorelmeasurablemapwe:K−→KandaBorelmeasurableprobabilityfun tionpe:K−→[0,1]begiven,i.e.Xpe(x)=1forallx∈K.e∈EWe allthefamilyD:=(K,we,pe)e∈Earandomdynami alsystem.Asurveyonrandomdynami alsystems anbefounde.g.in[23℄.
fareaderdoesn'tsee,howthedenitionofrandomdynami alsystemin[23℄relatestothatinthispaper,itisexplainedin[24℄.1 Withtherandomdynami alsystemDisasso iatedaarkovoperatorUa tingonallboundedBorelmeasurablefun tionsfbyXUf:=pef◦wee∈Eanditsadjointoperatora tingonthesetofBorelprobabilitymeasuresνbyZU∗ν(f):=U(f)dν.Ameasureµis alledinvariantwithrespe ttotherandomdynami alsystemsifandonlyifU∗µ=µ.+etΣ:={(σ1,σ2,...):σi∈E,i∈N}endowedwiththeprodu ttopologyof+−→Σ+dis reettopologiesandS:Σbetheleftshiftmap.Forx∈K,letPx+betheBorelprobabilitymeasureonΣgivenbyPx(1[e1,...,en]):=pe1(x)pe2◦we1(x)...pen◦wen−1◦...◦we1(x),+forevery ylinderset1[e1,...,en]:={σ∈Σ:σ1=e1,...,σn=en},whi hisasso iatedwiththearkovpro essgeneratedbytherandomdynami alsystemwiththeDira initialdistributionδx.Remark1otethatea hmapweneedstobedenedonlyonasubsetofKwhereitsprobabilityfun tionpeisgreaterthanzero.
nthis ase,oneobtainsarandomdynami alsystemonKbyextendingthemapsonthewholespa earbitrarily.1.1Histori al ontextFirst,
willgivesomehistori alrootsofthetheory,andthen,
willlistsomeworkswhi hinmyviewformthehistori al ontextofthispaper.
twasnot learuntilthebeginningofthetwentieth enturywhetherthein-dependen eofrandomvariablesisane essary onditionforthelowoflargenumbersandtheentrallimittheoremtohold.ThebreakthroughwasaworkbyA.A.arkov[26℄inwhi hhehasextendedthelowoflargenumberstodependentrandomvariables(healsoextendedthe entrallimittheoremtosu hpro esses,see[11℄forani ea ountonarkov'sworkandlife).arkovre-stri tedhimselftopro esseswhereea hrandomvariabledependsonlyonthepreviousone.Su hapro ess,in aseofadis reetstatespa e,isgeneratedbyatransitionmatrix(oradire tedgraphwithprobabilityweights)andaninitialdistribution.Thesepro esses,nowknownasarkov hains,foundmanyappli ations.2 Fromtheworkofarkovnaturallyarisesthequestionwhetherthelowoflargenumbersandotherlimittheoremsholdtrueforamoregeneral lassofdepen-dentpro esses.Thetrulynext lassofpro esses anbeonlythosewherethedependen eofarandomvariableonthepastisnotrestri tedtoanynumberofpreviousvariables.Thestudyofsu hpro esseswasinitiated(andmotivatedbyappli ations)by.ni es uandG.iho[27℄.Remarkably,theyfoundawayof onstru tingsu hpro esseswithoutgivinginnitelymanyrulesofdepen-den eofarandomvariableonthevaluesofallprevious,whi hisof ourseveryimportantforappli ations.They alledsu hpro essesles haînesàliaisonsomplètes.Theirworkgaverisetothetheoryofdependen ewithompeteon-ne tions,inwhi hmanylimittheoremshavebeenproved[17℄.What
allinthispaperrandomdynami alsystem anbeseenasaspe ial aseofthistheory.However,itmustbesaidthateverystationarypro esswithvaluesinE analreadybegeneratedbysu harandomdynami alsystem.et'sillustratethedependen einthenotationofthispaper.
fmapsweare ontra tionsona ompletemetri spa e,thepastis odedbythemapstoapointintopologi alspa eKandtheprobabilityofavaluefromEofthenextrandomvariableisthenobtainedasafun tionevaluatedatthatpoint,P(X1=e1|X0=e0,X−1=e−1,...)=pe1limwe0◦we−1◦...◦we−n(x0)n→−∞Zforall(...,e−1,e0,e1,...)∈Eandx0∈K.ne ouldarguethatthedevelopmentsofarwasguidedmainlybytheinter-nalmathemati allogi .However,themainreasonforthedevelopmentofthemathemati allanguagestillisthestrivingofHomoSapiensforabetterdes rip-tionoftheworldoutside(evenifmanymodernmathemati al raftsmenhavenointerestins ien eatall).Therandomdynami alsystemssu hasinthispaperarosenaturallyalsoaslearningmodels[20℄,[9℄.Consideranintelligentobje t,e.g.arat.
tsstateof"intelligen e"xisassumedtotakesomevaluefrom[0,1]⊂R.Theobje tis"askedsomequestions"anditsresponsesaremeasuredas'0'("wrong")or'1'("right").
fitgivesananswer'0',its"intel-ligen e"ismovedtow0(x):=1/2x.therwise,its"intelligen e"ismovedtow1(x):=1/2x+1/2.
tisnaturaltoassumethataresponse'0' anhappenwithsomeprobabilityp0(x)(dependingonthe urrentstateof"intelligen e")andaresponse'1'withprobabilityp1(x):=1−p0(x).neassumesthatthefun tionp0doesnothangewiththetime(ifitdid,it'slikelythatitwouldhavesometimeaverage,whi honlywouldmatter[3℄).Furthermore,probabil-ityfun tionsp0andp1easily anbeobtainedempiri allyifsu ientlymanymeasurementsaremade.anyseminalworksonarkovpro essesgeneratedbyrandomdynami alsystemshavebeenmotivatedbylearningmodels.Thestrivingfora lassi ationofstationaryrandompro essesbroughtattentiontosu hsystemson eagain.Afterrnstein[28℄hadshownthatolmogorov-Sinaientropyisa ompleteinvariantonBernoullishiftsandnot ompleteonolmogorovautomorphisms[29℄,aroseaninterestinmeasurepreservingtrans-3 formationswhi hareolmogorovandnotBernoulli.f ourse,anatural andi-dateforthatisastronglymixingpro essonanitealphabetwithinnitemem-ory,whi hisknowntobegeneratedbythesekindofrandomdynami alsystems.
twas.eane[21℄whodrewattentionofergodi theorypeopletosu hsys-tems.He onsideredaspe ial asewherethemapsofthesystem anbeobtainedasinversebran hesofa(expanding)homomorphismSofa ompa tmetri spa eKN∪0(e.g.K:=EandSisshiftmap,thenwe(...,y−1,y0):=(...,y−1,y0,e)forall(...,y−1,y0)∈K).
nthis ase,theprobabilitiesforthesemaps anbegivenintermsofafun tiong:K−→[0,1](peP(...,y−1,y0):=g(...,y−1,y0,e)forall(...,y−1,y0)∈K)withthepropertythaty∈S−1({x})g(y)=1forallx∈K).Thenthestationarypro essalsoisinvariantwithrespe ttohomomorphismS.He alledthestationarypro essinthis aseag-measure.u hoftheprogressonthesubje thasbeenmadefromthestudyofthisspe ial ase.f ourse,theone-sidedsymboli spa eismorethanjustanexample.However,therestri tiontothis ase learlyen ouragesanalgebrai ratherthanageometri approa h,whi h ouldbeoneofthereasonswhythestru tureofthefundamentalarkovsystem,whi hisgoingtobeintrodu edinthispaper, annothavebeenseenbefore.A arefulreaderprobablyhasnoti edthatinalloftheexamplessofarthemapsofthesystemhavebeen ontra tive.
twasshownby.Hut hinson[16℄thatafamilyof ontra tivemapsona ompa tmetri spa ehasauniqueinvariantsubset.Thesesubsetsarelikefootprintsofthiskindof"animals".Theyareoftenveryirregularoneverys ale.(Thismustbeveryfas inatingalreadyforitselfbe ausethereareevenpeoplewhostudythesefootprintswithouta tuallyanyinterestinany"animal".)Advan esin omputationalte hnologyallowedtoprodu ebeautiful olorfulpi turesofsu hsets.aturally,arosetheideaofstoringimageswithsu hsystems[14℄.oreover, ontra tivemapsallowto odestringsofsymbolssu has'0'and'1'toapointinthestatespa e.This anbeusefulfordata ompression[4℄.Thisallattra tedanewinteresttotherandomdynami alsystems.Thestudyofsu hsystemsforthesepurposeswas ontinuedmainlyby.F.Barnsleyetal.[1℄,[2℄.They alledthemiteratedfun tionsystemswithpla edependentprobabilities.u hoftheliteratureonthesubje tisnowavailablealsounderthisname.Re ently,su hsystemhavebeensuggestedalsoasanaturalmodelforaquantummeasurementpro ess[31℄.etKbeastatespa eofaquantumsystemandEasetofpossibleoutputsofameasurementapparatus.Whenthequantumsystembeinginastatex∈Kintera tswiththemeasurementapparatusandweobservee∈E,itisknownthatthisusuallyresultsinthesystemmovingtoanewstatey∈K.Hen e,itisnaturaltoassumethatthereisamapwe:K→Kasso iatedwithea houtpute∈E.oreover,itisnaturaltoassumethate ouldbeobservedwithsomeprobabilitype(x)inthisexperiment.Thisallalso anbeformulatedusingthe onventionallanguageofHilbertspa eandproje tionoperators[31℄.Thereaderprobablyhasnoti edtheanalogywiththesetupofthe"learningmodel"above.
tprobablyisanindi ationontheuniversalityoftheapproa h.
nfa t,studyingasystembyaskingitsome4 "question"isaverynaturalapproa h.
hope
have onvin edthereaderthatthestru turewhi hisbeingstudiedinthispaperisnotoneofthetoysdesignedbysomemathemati ianstokeepthembusy,butonewhi hnaturallyhasbeen rystalizinginthemoderns ien e.
t learlyneedstobeproperlyintegratedintothebodyofmathemati swhi hdes ribesdeterministi ,randomandquantumparadigms.ow,
willlistsomeimportant ontributionswhi hweremadeforthepurposeofunderstandingsu hsystemswithrespe ttotheirstabilityandergodi propertieswhi h learlyformthehistori al ontextofthispaper.W.DoeblinandR.Fortet[12℄(1937)gavefairlyweak onditiononstri tlypositiveprobabilityfun tionsona ompa tmetri spa ewhi hinsuresthatthesystemwith ontra tivemapshasaunique(attra tive)stationaryinitialdistribution.
nparti ular,this onditionissatisediftheprobabilitieshaveasummablevariation(Dini- ontinuous)..Breiman[9℄(1960)provedthestronglowoflargenumbersforarkovopera-torswiththeFellerpropertywhi hpossesauniquestationaryinitialdistributionona ompa tHausdorfspa e(seeasharperresultin[37℄).R.
saa [18℄(1962)introdu edtheaverage ontra tiveness ondition,whi hinsurestheuniquenessofthestationarystate(heproveditona ompa tmetri spa ewithstri tlypositiveprobabilityfun tionssatisfyingips hitz ontinuity).F.edrappier[25℄(1974)identiedtheg-measuresasproje tionsofsomeequi-libriumstatesdenedbyvariationalprin iplewithrespe ttothepotentialloggZseenasafun tiononE(see[38℄fortheexplanationinthegeneral ase).Furthermore,heshowedthatthenaturalextensionoftheg-measureisweaklyBernoulliiftheg-fun tionisstri tlypositiveandDini- ontinuous..Walters[33℄(1975)extendedtheresulttosu hgonasubshiftofnitetype(arkovsystem).T.aijser[22℄(1981)introdu edalo al ontra tivenessonaverage onditioninthegeneralsetupofrandomsystemswith omplete onne tions,whi halso animplytheuniquenessofthestationarystate.He alledhissystemsweaklydistan ediminishingrandomsystemswithompleteonne tions.H.Berbee[5℄(1987)showedtheuniquenessandtheveryweakBernoulliprop-ertyoftheg-measureforstri tlypositiveg-fun tionsonafullshiftsatisfyinga ontinuity onditionwhi hisweakerthantheDini- ontinuity.Afterthat,manyotherworkshavebeendevotedtotheweakeningofthealgebrai expressionfor -inga ontinuityoftheg-fun tion,butmostlyonlyfortheproofofuniquenessofthestationarystate(seeÖ.Steno[30℄(2003)and.Berger,Ch.Homan,V.Sidoravi ius[6℄(2005)andthereferen esthere).(
tmustbepointedoutthatthe ontinuityoftheprobabilityfun tionsisnotfundamentalforthestabilityofsu hsystems(e.g.Example2))..H.Elton[13℄(1987)re ognizedtheimportan eoftherelationforx,y∈Kgivenbytheequivalen eofmeasuresPxandPyfortheproofoftheergodi 5 theoremforsu hsystems(though,hestillassumedtheuniquenessofthesta-tionarystate,whi hwasshownlater[35℄tobenotne essary).Heprovedthatthisequivalen erelationholdstrueforallx,y∈Kifallprobabilityfun tionsareboundedawayformzero,Dini- ontinuousandthesystemsatisesa ontra -tivenessonaverage ondition(inthelanguageofthispaper,thefundamentalarkovsystemasso iatedwithsu harandomdynami alsystemhasasinglevertexset)..F.Barnsley,S.G.Demko,.H.Eltonand.S.Geronimo[1℄[2℄(1989)made,inmyview,twoimportant ontributionstounderstandingthe onditionsforthestabilityofsu hsystems.Theyshowedthatthe onditionofthestri tpositivityoftheprobabilityfun tions anbeweakened(isnotfundamental).Se ondly,theyfoundimpli itlyawayofredu tionofthemultipli ativeaver-age ontra tiveness onditiontotheadditiveaverage ontra tiveness ondition,thoughtheydidnota omplishit ompletely(see[34℄fordetails).
.Werner[35℄(2005)showedthatthe onditionofequivalen eofmeasuresPxandPyforallxandyinthesamevertexsetofaarkovsystem(seenextse tion),whi his ontinuous,irredu ibleand ontra tive,issu ientfortheuniquenessofthestationaryinitialdistribution.Forexample(theexamplewasgivenbyusingsomeideasofA.ohanssonandA.Öberg[19℄),this onditionissatisediftheprobabilityfun tionshaveasquaresummablevariationonea hvertexsetandareboundedawayfromzero,whi hismoregeneralthanElton's[13℄example.Thislistisfarfrombeing omplete.Therearemanyotherworks,whi hareader aneasilyndunder odenamesg-measures,iteratedfun tionssystemswithpla e-dependentprobabilities,randomsystemswithompleteonne tions,randomdynami alsystemsandarkovsystems.Areaderinterestedinthestudyofgeneralarkovoperatorsisreferredto[32℄.1.2arkovsystemsow,letus onsideraspe ialrandomdynami alsystemwhi hwe allaarkovsystem[34℄.etK1,K2,...,KNbeapartitionofametri spa eKintonon-emptyBorelsub-sets(wedonotex ludethe aseN=1).Furthermore,forea hi∈{1,2,...,N},letwi1,wi2,...,wiLi:Ki−→KbeafamilyofBorelmeasurablemapssu hthatforea hj∈{1,2,...,Li}thereexistsn∈{1,2,...,N}su hthatwij(Ki)⊂Kn(Fig.1).Finally,forea hi∈{1,2,...,N},letp,p,...,p:K−→R+i1i2iLiibeafamilyofpositiveBorelmeasurablePprobabilityfun tions(asso iatedwithLithemaps),i.e.pij>0foralljandj=1pij(x)=1forallx∈Ki.6 N=3K2'$we1&%we3we2we6(((((T

we4J
JT
JTT
JJK1we5K3Fig.1.Aarkovsystem.Denition1We allV:={1,...,N}thesetofverti esandthesubsetsK1,...,KNare alledthevertexsets.Further,we allE:={(i,ni):i∈{1,...,N},ni∈{1,...,Li}}thesetofedgesandweusethefollowingnotations:pe:=pinandwe:=winfore:=(i,n)∈E.Ea hedgeisprovidedwithadire tion(anarrow)bymarkinganinitialvertexthroughthemapi:E−→V(j,n)7−→j.Theterminalvertext(j,n)∈Vofanedge(j,n)∈Eisdeterminedbythe orrespondingmapthrought((j,n)):=k:⇐⇒wjn(Kj)⊂Kk.We allthequadrupleG:=(V,E,i,t)adire ted(multi)graphordigraph.Asequen e(niteorinnite)(...,e−1,e0,e1,...)ofedgeswhi h orrespondstoawalkalongthearrowsofthedigraph(i.e.t(ek)=i(ek+1))is alledapath.
Denition2We allthefamilyM:=Ki(e),we,pee∈Ea(nite)arkovsystem.Thedenition anbeeasilygeneralizedtotheinnite ase.Thearkovsystemdenesarandomdynami alsystemonKbyextendingtheprobabilityfun tionspe|Ki(e)onthewholespa ebyzeroandthemapsarbitrarily,asinRemark1.7 Denition3We allaarkovsystemirredu ibleoraperiodi ifandonlyifitsdire tedgraphisirredu ibleoraperiodi respe tively.Denition4(CS)We allarkovsystemMontra tivewithanaverageontra tingrate00hasauniqueinvariantBorelprobabilitymeasureifPx≪Pyforallx,y∈Ki(e),e∈E,andthesubsetsKiformanopenpartitionofK(thiswasshownin[35℄forsomelo ally ompa tspa es,butitholdsalsoon ompleteseparablespa es,as ontra tiveMalsopossesinvariantmeasuresonsu hspa es[15℄).1.3Fundamentalarkovsystemsow,weintendtoshowthatwitheveryrandomdynami alsystemDisasso-′′′′′ iatedanequivalentarkovsystemM:=(Ki(e),we,pe)e∈E(notne essarily′≪P′′′′nite)su hthatPxyforallx,y∈Ki(e),e∈E,andea hKi(e)isthe′largestwithsu hproperty,wherePxaretheprobabilitymeasuresonthe ode′spa eofM.′The onstru tionofMgoesasfollows.Deneanequivalen erelationbetweenx,y∈Kbyx∼y:⇔Px≪≫Py,wherePx≪≫PymeansPxisabsolutely ontinuouswithrespe ttoPyandPyisabsolutely ontinuouswithrespe ttoPx.et]K′=Kii∈V′bethepartitionofKintotheequivalen e lasses.Then,foreverye∈Eandx,y∈K′′i,i∈V,pe(x)=0⇔pe(y)=0.′Hen e,foreverye∈Eandi∈V,′′eitherpe|Ki=0orpe|Ki>0.(2)Furthermore,holdsthefollowing.8 ′′′roposition1Foreverye∈Eandi∈Vwithpe|Ki>0,thereexistsj∈V′′su hthatwe(Ki)⊂Kj.′roof.etx,y∈Ki.bservethatPx(1[e,σ1,...,σn])=pe(x)Pwe(x)(1[σ1,...,σn])forevery ylinderset1[σ1,...,σn].Hen e,P(S−1(B)∩[e])x1Pwe(x)(B)=pe(x)+foreveryBorelB⊂Σ.Sin etheanalogousformulaholdstruealsoforPwe(y),(x)∼w(y)′′we on ludethatwee.Thus,thereexistsj∈Vsu hthatwe(Ki)⊂K′j.2By(2)androposition1,we andeneaarkovsystemsasso iatedwithD.Denition5et′′Ei:={(i,e):pe|K′>0,e∈E}foralli∈Viand[E′:=E′.ii∈V′′′′′Forevery(i,e)∈Esetp(i,e):=pe1K′,w(i,e):=we|K′,i((i,e))=iandiit′((i,e))=j′′′′′′′wherewe(Ki)⊂Kj.ThenG:=(V,E,i,t)isadire ted′′′′′graphandwe allM:=(Ki(e),we,pe)e∈Ethefundamentalarkovsystemsasso iatedwiththerandomdynami alsystemD.′ow,weneedtoshowthatthevertexsetsofthefundamentalarkovsystemM′asso iatedwithDaremeasurable.therwise,possibleBana h-Tarskiee tsmightmakeour onstru tions ienti allyirrelevant.Forthat,weneedtomake learthe onstru tivenatureoftheequivalen erelationwhi hdenesthevertexsets.Forx,y∈K,letPx(1[σ1,...σn])Py(1[σ1,...σn]),Py(1[σ1,...σn])>0Xn(σ):=0,Px(1[σ1,...σn])=0∞,Px(1[σ1,...σn])>0andPy(1[σ1,...σn])=0andPy(1[σ1,...σn])Px(1[σ1,...σn]),Px(1[σ1,...σn])>0Yn(σ):=0,Py(1[σ1,...σn])=0∞,Py(1[σ1,...σn])>0andPx(1[σ1,...σn])=09 +forallσ∈Σ.Deneξ(x,y):=limsupsupPx(Xn>M)+limsupsupPy(Yn>M).M→∞n∈NM→∞n∈Nbservethatea hx7−→Px(1[σ1,...σn])isaBorelmeasurablefun tion.There-fore,ea hx7−→Px(Xn>M)isaBorelmeasurablefun tion.Hen e,x7−→ξ(x,y)isaBorelmeasurablefun tionforally∈K.Bythesymmetry,alsoy7−→ξ(x,y)isaBorelmeasurablefun tionforallx∈K.emma1Forallx,y∈K,ξ(x,y)=0ifandonlyifPx≪≫Py.+roof.etx,y∈K.etAnbetheniteσ-algebraonΣgeneratedbythe ylinders1[σ1,...σn].ow,observethat,forallm≤nandCm∈Am,ZZXXndPy=Px(Cn)=Px(Cm)=XmdPy.(3)Cn⊂CmCmCmHen e,(Xn,An)n∈NisaPy-martingale.Analogously,(Yn,An)n∈NisaPx-martingale.oreover,by(3),ZPx(Xn>M)=XndPy{Xn>M}andanalogouslyZPy(Yn>M)=YndPx.{Yn>M}Hen e,ZZξ(x,y)=limsupsupXndPy+limsupsupYndPx.M→∞n∈NM→∞n∈N{Xn>M}{Yn>M}Therefore,ξ(x,y)=0ifandonlyifXnandYnareuniformlyintegrablemar-1tingales.Hen e,the onditionξ(x,y)=0impliesthatthereexistsX∈L(Py)11andY∈L(Px)su hthatXn→XandYn→YbothinLsense,andEPy(X|Am)=XmPy-a.e.andEPx(Y|Am)=YmPx-a.e.forallm.Then,by(3),ZZXdPy=XmdPy=Px(Cm)forallCm∈Am.CmCmHen e,theBorelprobabilitymeasuresXPyandPxagreeonall ylindersubsets+ofΣ,andtherefore,areequal.Analogously,YPx=Py.Thus,Px≪≫Py.Conversely,Px≪≫PyimpliesthatXnandYnareuniformlyintegrable[7℄,i.e.ξ(x,y)=0.210 Remark2otethatitisnotobviousfromthedenitionofξthattherelationξ(x,y)=0istransitive.′′roposition2(i)ThevertexsetsKi,i∈V,areBorelmeasurable.′′|′(ii)Considerallprobabilityfun tionspeKi(e),e∈E,tobeextendedonKby′′′′zeroandallmapswe|Ki(e),e∈E,tobeextendedonKarbitrarily.etUbe′′thearkovoperatorasso iatedwiththearkovsystemM.ThenU=U,i.e.M′isanequivalentrandomdynami alsystemtoD.′′roof.(i)eti∈V.Fixy∈Kiandsetf(x):=ξ(x,y)forallx∈K.Then,′−1′byemma1,Ki=f({0}).Hen e,asfisBorelmeasurable,KiisBorelmeasurable.(ii)etgbeaboundedBorelmeasurablefun tiononKandx∈K.Thenthere′′existsauniquei∈Vsu hthatx∈Ki.Hen e,bythedenitionofM,XXXU′g(x)=p′(x)g◦w′(x)=p′(x)g◦w′(x)=p(x)g◦w(x)eeeeeee∈E′e∈E′e∈Ei=Ug(x).2Example1Supposetherandomdynami alsystemDisgivenbythe on-tra tivearkovsystemMsu hthatthevertexsetsK1,...,KNformanopenpartitionofKandtheprobabilityfun tionspe|KPi(e)areboundedawayfrom2nzeroandhaveasquaresummablevariation,i.e.n∈Nφ(a)<∞,whereφisthemaximumofmodulesofuniform ontinuityoffun tionspe|Ki(e),e∈E.Then,byemma2in[35℄,Px≪Pyforallx,y∈Ki,i=1,...,N(notethattheopennessofthepartitionwasrequiredin[35℄onlytoinsurethatMhasaninvariantmeasure(Fellerproperty)).Therefore,thefundamentalarkovsystemasso iatedwithMisMitself.Example2etD2:=([0,1],we,pe)e=0,1betherandomdynami alsystemwherew0(x)=x/3,w1(x)=x/3+1/3forallx∈[0,1],0,0≤x≤1p0(x)=19,b,>Pyforallx,y∈Ki,i=0,1,2.etx∈K0andy6∈K0.ThenPx(1[0])=0,butPy(1[0])=b>0.ow,letx∈K1andy6∈K1.
fy∈K0,thenPy(1[0])=0,butPx(1[0])=b.therwise,ify∈K2,Px(1[00])=0,butPy(1[00])=b.The laimfollows.2ow,we anapplyTheorem2in[36℄toanequivalentfundamentalarkovsystemonadis onne tedset,thevertexsetsofwhi hareK˜0:=[0,1/9],K˜1:=[2/9,1/3]andK˜2:=[2/3,1].(otethatthereisamissprintin[36℄onpageA˜:=D−1AtD471.
tshouldbe.)ByTheorem2in[36℄,D2hasaunique22invariantBorelprobabilitymeasureµ2withµ2(K0)=b/(1+b+b),µ2(K1)=b/(1+b+b2)2andµ2(K2)=1/(1+b+b)andthearkovhainasso iatedwithD2isgeometri allyergodi witharelativerateof onvergen einonge-1/2antorovi hmetri lessorequaltomax{1/3,b}.
fwerepla ep0with0,0≤x≤1p0(x)=127,b,0,followsPx<0,thereexistsaunique ylinderset[e,...,e]⊂Σ+′′′])=P([e,...,e])′′11nsu hthatPy(1[e1,...,eny11nandΨ(1[e1,...,en])=1[e1,...,en].Hen e′′′′′])).Py(1[e1,...,en])=Py(Ψ(1[e1,...,en(4)′′ow,letB⊂ΣBorelmeasurablesu hthatPy(B)=0.etǫ>0.Bythehypothesis,thereexistsδ>0su hthatPy(C)<δ⇒Px(C)<ǫ(5)+′forallBorelmeasurableC⊂Σ.BytheBorelregularityofPx,thereSexistsa′+C ounStablefamilyof ylindersetsCk⊂Σ,k∈N,su ShthatB⊂kkand′C)<δmCPy(kk.SSin ewe anwriteeveryniteunionkkasadisjointunionnmC˜of ylindersetskk,X∞[′′Py(C˜)=Py(Ck)<δ.k=1kHen e,by(4)andtheemma2,[X∞X∞P(Ψ(C))≤P(Ψ(C˜))=P′(C˜)<δ.ykyykk=1k=1Therefore,by(5)andemma2,[P′(B)≤P′(Ψ−1(Ψ(B)))=P(Ψ(B))≤P(Ψ(C˜))<ǫ.xxxxkkSin eǫwasarbitrary,this ompletestheproof.214 Theorem1SupposeDisarandomdynami alsystemwithnitelymanyuni-formlyontinuousprobabilityfun tionspeandontinuousmapsweonaom-pleteseparablemetri spa eK.Supposethatthefundamentalarkovsystemasso iatedwithDhasnitelymanyverti es,isirredu ibleandontra tive.Then(i)DhasauniqueinvariantBorelprobabilitymeasureµ.(ii)Foreveryx∈K,nX−1Z1+nf◦wσk◦...◦wσ1(x)→fdµforPx-a.e.σ∈Σk=oforallboundedontinuousfun tionsf.roof.ApplyTheorem4in[35℄forthefundamentalarkovsystemasso iatedwithDwiththefollowingjusti ations.
n[35℄,thevertexsetswererequiredtoformanopenpartitionofastatespa einwhi hsetsofnitediameterarelatively ompa t.ThiswastoinsurethatthearkovoperatorhastheFellerpropertyandaninvariantBorelprobabilitymeasure.Here,theFellerpropertyisalreadygivenbyDandtheexisten eofinvariantmeasuresforourfundamentalarkovsystemasso iatedwithD(on ompleteseparablespa e)wasshownin[15℄.Also,itwasrequiredin[35℄thattheprobabilityfun tionspe|Ki(e)shallbeboundedawayfromzero,butitwasonlyrequiredfortheproofthatPx≪Pyforallxandyinthesamevertexset(emma2in[35℄).Thelatterisgivenherebythe onstru tionofthefundamentalarkovsystemasso iatedwithDandroposition3.Afterobtainingtheresultforthefundamentalarkovsystemasso iatedwithD,dedu etheresultforDbyroposition3.2′Remark3otethatthefundamentalarkovsystemMasso iatedwithDis ontra tiveifDis ontra tive.Remark4Re allthatthereexist ontra tiverandomdynami alsystemswithstri tlypositive ontinuousprobabilityfun tionswhi hhavemorethanoneprobabilitymeasure[8℄,[6℄.ByTheorem1thefundamentalarkovsystemasso iatedwithsu harandomdynami alsystem annothaveasinglevertexset.Conje ture1
believethatfundamentalarkovsystemsresolvethequestionofthene essaryandsu ient onditionforthestabilityofsu hrandomdy-nami alsystems,whi hhasbeenopenalreadyformorethan70years,inthefollowingway.Therandomdynami alsystemhasauniqueinvariantBorelprob-abilitymeasureifandonlyifthefundamentalarkovsystemasso iatedwithitisre urrent(everyvertexofitisrea hedfromanyotherbyanitepath).otethatare urrentarkovsystemisne essarily ountable(everyvertexofit anbe odedbyanitepath).15 Referen es[1℄.F.Barnsley,S.G.Demko,.H.Eltonand.S.Geronimo,
nvariantmeasureforarkovpro essesarisingfromiteratedfun tionsystemswithpla e-dependentprobabilities,Ann.
nst.Henrioin aré24(1988)367-394.[2℄.F.Barnsley,S.G.Demko,.H.Eltonand.S.Geronimo,Erratum:
n-variantmeasureforarkovpro essesarisingfromiteratedfun tionsystemswithpla e-dependentprobabilities,Ann.
nst.Henrioin aré25(1989)589-590.[3℄.F.Barnsley,.H.EltonandD..Hardin,Re urrentiteratedfun tionsystems,Constru tiveApproximation5(1989)3-31.[4℄.F.Barnsley,A.Deliu,R.Xie,Stationarystohasti pro essesandfra taldata ompression,
nt..Bifuration&Chaos7(1997),551-567.[5℄H.Berbee,Chainswith
nniteConne tions:UniquenessandarkovRep-resentation,robab.Th.Rel.Fields76(1987),243-253.[6℄.Berger,Ch.Homan,V.Sidoravi ius,onuniquenessforspe i ations2+ǫinℓ,arXiv:math/0312344v4.[7℄.Billingsley,robabilityandeasure,ohnWileyandSons(1979).[8℄.Bramson,S.alikowonuniquenessing-fun tions,
srael.ath.84(1993)153-160.[9℄.Breiman,Thestronglawoflargenumbersfora lassofarkovhains,Ann.ath.Stat.31(1960)801-803.[10℄.Brémaud,arkovChains:Gibbselds,onteCarlosimulation,andqueues,Springer(1998).[11℄G..Basharina,A..angvilleandV.A.aumov,ThelifeandworkofA.A.arkov,inearAlgebraanditsAppli ations386(2004)3-26.[12℄W.DoeblinandR.Fortet,Surleshaînesàliaisons omplètes,Bull.So .ath.Fran e65(1937)132-148.[13℄.H.Elton,Anergodi theoremforiteratedmaps,Ergod.Th.&Dynam.Sys.7(1987)481-488.[14℄.H.EltonandZ.Yan,Approximationofmeasuresbyarkovpro essesandhomogeneousaneiteratedfun tionsystems,Constru tiveApproxima-tion5(1989)69-87.[15℄.Horba zandT.Szarek,
rredu iblearkovsystemsonolishspa es,Studiaath.177(2006),285-295.[16℄.Hut hinson,Fra talsandSelf-Similarity,
ndianaU..ofath.30(1981),713-747.16 [17℄.
osifes u,.Grigores u,Dependen ewithompleteonne tionsanditsappli ations,CambridgeTra tsinathemati s,96.CambridgeUniversityress,Cambridge,(1990).[18℄R.
saa ,arkovpro essesanduniquestationaryprobabilitymeasures,a i .ath.12(1962)273-286.[19℄A.ohanssonandA.Öberg,Squaresummabilityofvariationsofg-fun tionsanduniquenessofg-measures,ath.Res.ett.10(2003)587601.[20℄S.arlin,Somerandomwalkso urringinlearningmodels,a i .ath.3(1953)725-756.[21℄.eane,Stronglyixingg-easures,
nventionesmath.16(1972)309-324.[22℄T.aijser,nanew ontra tion onditionforrandomsystemswith om-plete onne tions,Rev.Roumaineath.uresAppl.26(1981)1075-1117.[23℄Y.iferand.-D.iu,Randomdynami s,HandbookofDynami alSystems,vol.1B(B.HasselblattandA.atokeds.),379-499,orth-Holland/Elsevier(2006).[24℄A.wie i«skaandW.Slom zy«ski,Randomdynami alsystemsarisingfromiteratedfun tionsystemswithpla e-dependentprobabilities,Statisti s&robabilityetters50(2000)401-407.[25℄F.edrappier,rin ipevariationneletsystèmesdynamiquessymboliques,Z.Wahrs heinli hkeitstheorieverw.Gebiete30(1974)185-202.[26℄A.A.arkov,Extentionofthelawoflargenumberstodependentevents(inRussian),Bull.So .hys.ath.azan,2(1906),no.15,155-156.[27℄.ni es uandG.iho ,Surleshaînesdevariablesstatistiques,Bull.S i.ath.deFran e59(1935)174-192.[28℄D.S.rnstein,Bernoullishiftswiththesameentropyareisomorphi ,Adv.inath.4(1970),339-348.[29℄D.S.rnsteinand.Shields,Anun ountablefamilyofK-automorphisms,Adv.inath.10(1973),63-88.[30℄Ö.Steno,Uniquenessing-measures,onlinearity16(2003)403-410.[31℄W.Slom zynski,Dynami alentropy,arkovoperators,anditereatedfun -tionsystems,RozprawyHabilita yjneUniwersytetuagiello«skiegor362,Wydawni twoUniwersytetuagiello«skiego(2003).[32℄T.Szarek,
nvariantmeasuresfornonexpansivearkovoperatorsonolishspa es,Diss.ath.415,1-62(2003).[33℄.Walters,Ruelle'speratorTheoremandg-measures,Tran.AS214(1975)375-387.17 [34℄
.Werner,Contra tivearkovsystems,.ondonath.So .71(2005)236-258.[35℄
.Werner,Contra tivearkovsystems

,arXiv:math/0506476.[36℄
.Werner,Contra tivearkovsystemwith onstantprobabilities,.The-oret.rob.18(2005),no.2,469-479.[37℄
.Werner,Ane essary onditionfortheuniquenessofthestationarystateofaarkovsystem,arXiv:math/0508054.[38℄
.Werner,n odingwithFeller ontra tivearkovsystems,arXiv:math/0506476.18