A perturbation theory for ergodic properties of Ma

APerturbationTheoryforErgodicPropertiesofMarkovChainsT.Shardlow12andA.M.Stuart1AbstractPerturbationstoMarkovchainsandMarkovprocessesareconsid-ered.Theunperturbedproblemisassumedtobegeometricallyer-godicinthesenseusuallyestablishedthroughuseofFoster-Lyapunovdriftconditions.Theperturbationsareassumedtobeuniform,inaweaksense,onboundedtimeintervals.Thelong-timebehaviouroftheperturbedchainisstudied.Applicationsaregiventonumer-icalapproximationsofarandomlyimpulsedODE,anIt^oSDEandaparabolicSPDEsubjecttospace-timeBrowniannoise.ExistingperturbationtheoriesforgeometricallyergodicMarkovchainsarenotreadilyapplicabletothesesituationssincetheyrequireverystringenthypothesesontheperturbations.KeyWords:MarkovChains,ErgodicTheory,NumericalApproxima-tion,RandomImpulses,StochasticDierentialEquations,StochasticPartialDierentialEquations.AMSSubjectClassications:60J10,60J27,65U,60H10,60H15,34A371ScienticComputingandComputationalMathematicsProgram,Durand257,Stan-fordUniversity,StanfordCA94305-4040,USA.SupportedbytheNationalScienceFoun-dationundergrantDMS-95-04879.2CurrentAddress:IMA,UniversityofMinnesota,514VincentHall,MinneapolisMN55455{04361IntroductionItisfrequentlyofinteresttounderstandhowergodicpropertiesofMarkovchainspersistundervariouskindsofperturbations.Hereperturbationsto(discretetime)Markovchainsand(continuoustime)Markovprocessesevolv-inginaBanachspaceareconsidered.Inbothcasestheperturbationisas-sumedtobeadiscretetimeMarkovchainandourprimarymotivationistounderstandthenumericalapproximationofMarkovchainsandprocesses.TheunperturbedMarkovchainisassumedtobegeometricallyergodicim-plyingexponentialconvergenceofexpectationsoffunctionsfromacertainclass;thegeneralframeworkofgeometricergodicitywithinwhichweoper-ateistakenfromtheworkofMeynandTweedie[20,21]basedonFoster-Lyapunovdriftconditions.TheperturbedMarkovchainsareassumedtobeclosetotheunperturbedprobleminaweaksense:theerrorinexpectationsoffunctionsissmall,uniformlyoncompacttime-intervalsdisjointfromtheorigin,forfunctionsinthesameclass.Perturbationtheoriesforgeometri-callyergodicMarkovchainsdoexistalready,butitturnsoutthattheclassofperturbationsconsideredthereistypicallytoorestrictivetoadmitappli-cationtothenumericalmethodsconsideredhere{atleastforthenitetimeapproximationresultsthatwearecurrentlyabletoobtainforthesenumeri-calmethods.Attheendofsection3wewillrelateourperturbationtheorytoanexistingperturbationtheoryduetoKartashov[13,14,15].PropertiesofergodicMarkovchainsunderperturbationhavebeenstudiedinmanyothercontexts;forexampleinSDEstheideaofapproximatingwhitenoisebyabroad-bandGaussiannoiseprocessisofinterestandthisisstudiedin[1]andfurtherin[17].Insection2ournotationandgeneralframeworkisestablished.Ageneraltheoryisdevelopedinsection3andthen,insection4,applicationsdescribedtothreeproblemswhere,inallcases,theperturbationarisesfromnumericalapproximation.TherstconcernsanODEsubjecttorandomimpulses,thesecondanIt^oSDE,andthethirdaparabolicSPDEsubjecttospace-timeBrowniannoise.ThenumericalsimulationofergodicstochasticprocessesinthecontextofnitedimensionalSDEshasbeenstudiedbyTalay[26]inthecasewherethegeneratoroftheprocessisuniformlyparabolic;seealso[27,10]and[16].Howeverinmanyapplicationsthisuniformparabolicitydoesnothold;ourtheoryencompassesproblemsforwhichthegeneratorisnotuniformly2parabolic,albeitatareducedrateofconvergencewhencomparedwiththeestimatesin[26].ForstochasticparabolicPDEs,muchisknownaboutap-proximationpropertiesonnitetimeintervals[4,8,11,23],butthetheorypresentedhereenablesustoprovelong-timeweakconvergencepropertiesinthegeometricallyergodiccase;suchresultshavenotbeenobtainedbeforetothebestofourknowledge.2PreliminariesInthefollowingN=f1;2;3;:::gandZ+=f0;1;2;:::g:LetSbeaBanachspaceandB(S)bethecorrespondingBorel{algebra.WeconsiderMarkovchainsfun;n2Z+g;(2.1)ofrandomvariablesfromaprobabilityspace(;F;P)to(S;B(S)).Foraninitialdistribution,lettheprobabilitytriple(;F;P)generatethechain(2:1).Weusethenotationxtodenoteapointmassatx2S:Expec-tationwithrespecttoPwillbedenotedbyE.Finally,wedenemeasuresnon(S;B(S));parameterizedby0=,accordington(B)=Pf!2:un2Bg;B2B(S):WeapproximatetheMarkovchain(2:1)byaMarkovchainfun;n2Z+g;(2.2)ofrandomvariablesfromaprobabilityspace(;F;P)to(S;B(S)).Foraninitialdistribution,theprobabilitytriple(;F;P)isassumedtogeneratethechain(2:2).ExpectationwithrespecttoPwillbedenotedbyE;thisshouldcausenoconfusionasitwillalwaysbeclearfromthecontextwhichunderlyingprobabilityspaceisgivingrisetotheexpectation.Inmanyapplicationstheunderlyingprobabilityspacesfor(2:1)and(2:2)willbethesamebutthisisnotnecessarilythecase,forexamplewhenweakapproximationsofstochasticdierentialequationsarestudied.Wedenemeasuresnon(S;B(S));parameterizedby0=,accordington(B)=Pf!2:un2Bg;B2B(S):3Wewillalsoconsidertheapproximationoftime-continuousMarkovpro-cessesbytime-discreteMarkovchainsoftheform(2:2).Specicallywecon-siderastochasticprocessfu(t);t0gofrandomvariablesfrom(;F;P)to(S;B(S)).Foraninitialdistribtuon,theprobabiltytriple(;F;P)gener-atesthisprocess.Foreach