; TeX output 1999.04.16:1726썠:-iӍ-s7"Vff cmbx10ErgoudicBeha=viourofAneRecursionsIsCriteria BforGRecurrenceandTransience*s+XQ cmr12HansG.KellerersMathematiscrhesInstitutderUniversit atMSvunchensTheresienstrae39,D-8000MSvuncrhen2,GermanrysOctobSer30,1992s0N cmbx12Summary.ThispapSerisconcernedwiththediscrete{timeMarkrovprocesss(,g cmmi12X2cmmi8nP)̹nK cmsy8 |{Ycmr804solvingthestoScrhasticdi erenceequationwhX̹n = Y̹nX̹n1D+ Z̹n *aforsnUR-!", cmsy102N,where(Y̹nP;Z̹n) n2t : cmbx9NJisasequenceofi.i.d.WrandomvXariablesindepSendenrtsoftheinitialvXariableX̸0and,inaccordancewithmostapplications,thestatesspacepbisrestrictedtoR̸+x.Thisresultsinquitenaturalnotionsof(topSological)srecurrence andtransienceandallorwsforratherexplicitcriteriatodistinguishsbSetrweenbothcases.Ӎs1991!MathematicsSubjectClassi cation.8KPrimary60H25,60J05;^Secondarys54H20.*썠:-iӍ{-sIntro`ductionsAdiscrete{timeMarkrovproScess(X̹nP)̹n0^withadecent(sayV,Polish)statespacesEcanibSegivrentheformofa\stocrhasticallyrecursivesequence"(inthesensesofBororvkov[4])m:@sX̹n=URg̹nP(X̹n1)for)n2N;swhereg̹nP;n2N;isasequenceofindepSendenrtandidenticallydistributedsrandomPmappingsfromEtoEwhicrhisindepSendentoftheinitialvXariableX̸0..A6 rst}systematictreatmenrtunderthisaspSectgoesbacrktoDubinsandsFVreedman[9],who,forE i=UR[0;1],consideredinparticulartrwocases:s(C)regardingpthemetricstructureofE,Dtheyrestrictedthemappingsg̹n ;tostheclassofconrtractions;s(A)spSecializingfurther,*atheylimitedthesemappingstotheclassofani-sties..Generalizationsgof(C):from[0,1]toacompletemetricspaceEM~attractedsmruch interestduringthelastdecade,mainlyinthecontextoffractals.'UnderstheKheading\iteratedfunctionsystems"BarnsleyV,kEltonandothersconsideredsquestionsconcerningstationarydistributions,3Rwreakconvergence,3Rrecurrence,sergoSdicitryUetc.zCrucialfortheirresultsisan\averagecontractivity"(see[2],s[3],[10],[11],[12])..ExtensionsEof(A)EwfromthecompactinrtervXal[0,1]toRoSccur rstinpaperssbry.Lev[27]andMasimov[29].qMorecomprehensiveareindepSendenttreat-smenrtsbyGrinceviscius[17]andVVervXaat[39].Explicitly,0anerecursionsonRsharvetheformofastoScrhasticdi erenceequationm:s()X̹n=URY̹nPX̹n1/t+Z̹nPfor.*n2Ns(whicrhP issomewhatmoregeneralthanX̹n 4=Y̹nN(X̹n1t{+Z̹nP)).iHere,icX̸0 isasrealrandomvXariable,ɞindepSendenrtofasequence(Y̹nP;Z̹n) n2NAofindependenrtsidenrticallydistributedR22-vXaluedrandomvariables..TheseOanerecursionsincludeasdegeneratecasesrandomwralks(Y̹n=UR1)sandin niteproSducts(Z̹n=UR0).ROfparticularinrterestarethe\additivemoSdel",swherem:@sX̹n=URyn9X̹n1/t+Z̹nPwithconstanrtfHyË2Rs(thesimplestcaseofanautoregressivreproScess),andthe\multiplicativemoSdel",swhere@sX̹n=URY̹nPX̹n1/t+zwithconstanrtaz52R:sBothJmoSdelscanbesubsumedunderthecasewhereY̹n (andZ̹nareindepSen-sdenrt..Due'totheparticularroleof0withrespSecttomrultiplication,thesituationissespSecially`vsimpleforP(Y=UR0)>0:`vThis\regenerativre"casecanbestudiedinsamoregeneralconrtext(seee.g.Nummelin[33]).Anotherparticularsituation@1썠:-iӍ{-sisprorvidedbythe\contractive"case,whereintheweakversionjY̹nPj`1andsinthestrongvrersionjY̹nPjUR#<1..TVoconcludethehistoricalremarks,trwocentralresultsconcerningthegen-seralcaseharvetobSemenrtioned:s|If&ananerecursionhasastationarydistribution,MbitisuniqueandthelarwssL(X̹nP)conrvergeweaklytoit,indepSendentlyoftheinitiallawL(X̸0).s|Conditions%ontheexistenceofastationarydistributioncanbSeformrulatedsvialogarithmicmomenrtsofY̹n andZ̹nP..ThepresenrtworkoriginatesintheobservXationthatmostapplicationsinseconomics,"GbiologyV,phrysics'etc.](seethelonglistofreferencesin[39])infactswrork.inthestatespaceR̸+x,andthusthecaseX̸0 Y0andY̹nP;Z̹n A0isofsspSecialэimportance.FVromthemathematicalpoinrtofviewthisrestrictionisssuppSortedIbrythefactthatastatespaceR̸+ fallowsonlyonekindofdivergencestoʠin nitryandtheassumptionY̹nP;Z̹n .H0entailsadditionalmonotonicityspropSertiesoftheassociatedtransitionkrernel..IntheexistingliteraturetheseaspSectsdonot ndmruchattention.Apartsfrom3anapproacrhbyLampSerti[25],"[26],too3generalforanerecursions,stherecareonlytrwocexceptions:*arecenrtpapSerbyMukherjea[30],couplingsintheconrtextofnonnegativematricesthesequence(X̹nP)̹n0withthepartialsproSductsof(Y̹nP) n2N,$^andapreprinrtbyRachev[34],$^concentratingoncentralslimittheoremsforsuitablynormalizedvXariablesX̹n inthedivrergentcase..TVoPsummarizethemainfeatureofthepresenrtworkbSeforegoingintodetails:sanerecursionsonR̸+ mseemtoprorvideoneofthebSestsuitedmodelsforsextendingMclassicalMarkrovMchaintheorytoanuncountablestatespace.FSincesthe$Harristheory(seee.g.U[35])iseasilyseennottobSeadequate,thestudyshasitobSebasedonthetopologicalstructure.This,ingeneral,leadstovXarioussnotionse`ofirreducibilitryandapSeriodicityV,ofe`(positivee`ornull)recurrenceandstransience*(seethepapSersbryRosenblatt[37]andTweedie[38]).Inthepresentscase,whorwever,these*notionsmergeinrtoverynaturalde nitionssatisfyingthesclassicalcriteria..ThisallorwsforarathercompletetheoryV,developSedinthesections:"S1.8LorweranduppSerlimit"S2.8Recurrenceandtransience"S3.8Recurrencecriteria"S4.8ExcessivreandinvXariantmeasures"S5.8ExistenceanduniquenessofinrvXariantmeasures"S6.8MainpropSertiesoftheinrvXariantmeasure"S7.8RatioergoSdictheorems"S8.8Prositiveandnrullrecurrence"S9.8FVurtherergoSdictheoremss10.8Theconrtractivecase.Thrus (thepapSerdividesintothreeparts: wSections1{3classifyanesrecursionsonR̸+ accordingtorecurrenceandtransience,Sections4{7treatsexistenceuanduniquenessofinrvXariantumeasuresaswrellasergoSdictheorems,@2Ϡ썠:-iӍ{-sSections8{10conrtinuetoclassifytherecurrenrtcasebyintroSducingtheno-stions?ofpSositivrerecurrenceandnullrecurrence.,PartISI5andIII5willappearins:::2and:::;theconrtentsofPrartIaresummarizedbSelow..SectionG1.CSinceconrvergenceofananerecursion,6eveninprobabilityV,soSccursZaonlyinanexceptionalcase(1.4),vPthelorwerZaandupperlimitareofin-sterest.TItisacrucialconsequenceofrestrictingthestatespacetoR̸+ mthatsthese)limitsareconstanrtsxfeR3and&feR]ڍx p{,indepSendentoftheinitiallawL(X̸0)(1.1).sWherevrerstarting,thesequence(X̹nP)̹n0oxapproachestheintervXal[xfeRR;&feR]ڍxP]mono-stonicallyc (1.2). WhiletheuppSerlimitonlydependsonthesupportofthesjoinrtlulawL(Y̹nP;Z̹n),thisingeneralfailsforthelorwerlimit.FInfact,itisnotssurprisingthatevreninthesimpleexample&s(E)X̹n=URY̹nPX̹n1/t+1with@Y̹n=UP2 1\|or-<2 +1stheasymptoticbSeharviourdependsessenrtiallyontheprobabilities@sp̺ q=URP(Y̹n=2 1 \|)and<,p̸+=P(Y̹n=2 +1 \|):sProrvided,ehowever,xfeRanddٟ&feR]ڍxwared nite,asimplecrharacterizationbymeansofsthesuppSortisarvXailable(1.3)..Section32.}ClearlyV,T(X̹nP)̹n0NKhastobSecalled\transienrt"inthecasexfeR #=UR1.sIt*islessclear{andoneofthecenrtralquestionsinthesequel{,whetherthessequencemarybSecalled\recurrent"inthecasexfeR!<1.Ab rstjusti cationsis*suppliedbryanequivXalentcharacterizationthroughtheassoSciatedpotenrtialskrernel:˸theWmeantimespSentinabSoundedintervXal[0;t]is niteinthetransientscaseơandin niteintherecurrenrtcase,providedt˽>xfeRQ(2.2).ExamplesơforsbSothsituationsareeasilyestablished:atheanerecursioniscertainlyrecurrenrtsin!theregenerativrecaseP(Y̹n E=f0)>0!(2.3),oanditistransientwheneversthe/assoSciatedrandomwralk(S̹nP)̹n0withincrementslogY̹n >divergesto+1s(2.4).3xThoughqbSothconditionsdependonthe\primary"vXariableY̹n onlyV,ݯthes\secondary"|vXariableZ̹n %HmarybSeessentialaswell.PInfact,howeversmallY̹n %His,sasucienrtlylargeZ̹n yieldstransience(2.5)..Section3.IInFtheadditivremoSdelanearlycompletecharacterizationofsrecurrenceNortransiencebrytheasymptoticbSehaviouroftP(log-IZ̹n \'>t)forst!1HYcanbSederivred,_whichHYextendstothecasewhereY̹n isboundedarwaysfrom1or0(3.1).aEThesituationislessclearinthemrultiplicativemoSdel.Itsisynotsurprisingthatinexample(E)CabSorveyp̺ ӄ< p̸+ impliestransienceandsp̺ q>URp̸+ impliesrecurrence.5Itisanonrtrivialproblem,uhowever,todecidethesbalancedpcasep̺ q=URp̸+x./Clearlytherelatedmrultiplicativeprandomwralk,where&@sX̸0V=UR1and<,X̹n=Y̹nPX̹n1for*n2N;soscillatesthroughthevXalues22k#;ko2URZ.!4ButitrequiresSpitzer'scomrbinatorialsidenrtitybtoprorvebthedriftterm+1nottocrhangerecurrenceintotransience.sTherelevXanrtrecurrencecriterionsettlesthemultiplicativemoSdelcompletelysandextendsinfacttothecasewhereZ̹n ;isonlybSounded(3.3).Assuming@3#-썠:-iӍ{-sY̹n nandƨZ̹ntobSeindependenrt,even nitenessoftheexpSectationofZ̹n nensuressrecurrence(3.4).*s0.PreliminariessThroughoutthepapSer(X̹nP)̹n0_isa xedanerecursiononR̸+x,givrenbythesstoScrhasticodi erenceequation()oftheintroSduction.Thusthedistributionofs(X̹nP)̹n0Hisg|completelydeterminedbrythelaws̸0=)L(X̸0)and=L(Y;Zܞ).sHere,=#Y1andZ_isbrie ywritteninsteadofY̹nandZ̹nP,aswillbSedonewhenevrersnUR2Nplarysnorole..Theinitiallarw̸0,F;asusual,islargelyofonlysecondarysigni cance.{ Ifsin4particular̸0 s8isaunitmeasure"̹xH,WthiswillbSeexpressedbrythenotations(X2xRAn:j)̹n0,i.e.p@sX xڍn :=URxY̸1Y̸2:::Y̹nR+Z̸1Y̸2:::Y̹nR+:::+Z̹nPfor.*xUR2R̸+ xand& n0:sThrusconditionalprobabilityandexpSectationaresimplygivenby@sP xH((X̹nP;nUR0)2B)=P((X xڍn:j;n0)2B);@sE xH(gn9(X̹nP;nUR0))=E(g(X xڍn:j;n0)):.RoughlyTspSeaking,whatfollorwsisatheoryofdistributionsronR22RA+x.%oHeresanessenrtialrolewillbSeplayedbytheirsuppSort,7forwhichthenotationNžwillsbSe" xed.SincenothingnewcanbeexpectedinthespecialcasesYQ!=1resp.sZ1=UR0,forsimpli cationp@sN\f(yn9;z)UR:yË6=1g6=;6=N\f(yn9;z):z56=0gsisalwraysassumed.NThesymbSolNkwillthroughoutrefertotheclassofdistri-sbutionsoonR22RA+  thatareadmissibleinthissense..As|isclearfromtheinrtroSduction,theergodicbeharviourof(X̹nP)̹n0EHisinti-smatelyrelatedtotherandomwralkp@sS̹n:=URCu cmex10CP㋟̸1mn0logAY̹mfor1 nUR0;sgeneralizedinthesensethatitmaryattainthe(absorbing)vXalue1.+RDuetosP(Y=51)<1BthereareonlythreepSossibilitiesfortheasymptoticbeharvioursofthisrandomwralk:ps(1)S̹n!UR+1 a.s. ;s(2)S̹n!UR1 a.s. ;s(3)S̹n!UR1 a.s. ;swherethesymrbSolin(2)servesasashortnotationfor@sP(liminf"̹n!1;2 S̹n=UR1;limsup*^̹n!1BS̹n=+1)=1:@45e썠:-iӍ{-.Another$proScesscloselyrelatedto(X̹nP)̹n0larisesif,inthenotationatthesbSeginningoftheinrtroduction,NtherandomvXariablesg̹n-V:::xZVg̸1(X̸0)arereplacedsbryg̸1j:::g̹nP(X̸0).8EspSeciallyforX̸0V=UR0thisyieldsuF@sW̹n:=URZ̸1j+Y̸1Z̸2+:::+Y̸1:::Y̹n1Z̹nPfor.*nUR0:sTheXsequence(W̹nP)̹n0RisnolongeraMarkrovXproScess,however,dueXtothesexcrhangeabilityof(Y̸1;Z̸1);:::ʜ;(Y̹nP;Z̹n),satis es@sL(W̹nP)UR=L(X 0ڍn)for)n0;sanequation,whicrhwillbSeimportanrtlateron..ThetransitionkrerneloftheMarkovproScess(X̹nP)̹n0willalwaysbSedenotedsbryP. Thus\thekrernelPtransformsanonnegativefunctionfintothefunctionsPf2givrenby@s(PfG)(x)UR=qCR f(yn9x+z)(dy;dz)sand1ameasureontheBoreln9{algebraB]m(R̸+x)inrtothemeasureP:givenby@s(P)(B)UR=qCR (f(yn9;z):yx+z52URBg)(dx):sIfisn9{ nite,thelastequationamounrtsto@s(P)(B)UR=( )(f(x;yn9;z)UR:yx+z52URBg):sInSaccordancewiththenotationsPfRandPHthe{inrtegralofafunctionfssometimesissimplydenotedbryfG..The|krernelPmenjoystwoimpSortantpropSerties.FirstitisclearlyaFVellerskrernel, transforming%bSoundedcontinuousfunctionsintothesametypSe.* More-sorver,+duetoYFq0,itismonotoneinthesensethatittransformsbSoundedsincreasingfunctionsinrtothesametypSe,too..IfeE6|isaloScallycompactspacewithacounrtablebase,Uthefollowingcon-sceptsfromtopSologicalmeasuretheorywillbeused:s|C5(E)ndenotesthespaceofbSoundedconrtinuousnfunctionsf~i:6jE!RnandsK,`(E)thesubspaceconsistingoffunctionsfQ2URC5(E)withcompactsuppSort.s|If isanrymeasureonB]m(E),VthenC̹ (E)denotesthespaceofbSoundedsBorel{measurablerfunctionsfR:SE:j!Rrthatare{almostevrerywherecontin-suousandK̹ (E)thecorrespSondingsubspace.s|TheclassM(E)ofloScally nitemeasuresonEM/isendorwedwiththevXagues(wreak*)topSologyV,i.e.8theinitialtopologywithrespecttothemappingsuF@sUR!f;fQ2K,`(E):sInthistopSologyconrvergencewillbedenotedbryRvg !.s|TheclassM̸1(E)ofprobabilitrymeasuresonEisendowedwiththeweaks(narrorw)topSologyV,i.e.8theinitialtopologywithrespecttothemappings@sUR!f;fQ2C5(E):sInthistopSologyconrvergencewillbedenotedbryøwg !.@5B썠:-iӍ{-.FinallyqithastobSeemphasizedthatstatemenrtsconcerningrandomvXari-sablespincaseofdoubtarealwrayspunderstoSodmoduloP{nrullsets.r7Thusthessupplemenrt\almostsurely",asinthetrichotomyconcerning(S̹nP)̹n0,willfre-squenrtlybSedeleted.*s1.Lowerandupp`erlimitsAsoutlinedintheinrtroSduction,thefollowingobservXationisofcentralimpSor-stancethroughoutthepapSer:s(1.1)Theorem..@ cmti12The35rffandomvariables@sX@sfe N{(:=URliminf%̹n!1>^X̹nPandfe fbX#A:=URlimsup)W̹n!1BX̹nsarffealmostsurelyconstantandindependentoftheinitialvalueX̸0,i.e.theresexist35cffonstants0URxfeR W&feR]ڍx1,35depffendingonlyon,suchthat@sP(Xfe A=URxURfeR )UR=1and6P(fe fbX=&feR]ڍx )=1:sPrffoof.1.8ThefollorwingfactwillbSeneeded:s(1)sup(̹n0;5rS̹n=UR+1 implies;supOb̹n0b-,X̹n=1 a.s.sIndeed,since@ssupT$ m2Nl%Z̹m Z>UR0a.s. andAsupUb̹nmkqe S;cmmi6n7Sm =1a.s. ;stheassertionisaconsequenceof@ssupT$̹n0fYX̹nUPsup m2N1+(Z̹m supj̹nm3~e Sn7Smw):.2.8LetXꨟfe xx&andꨟfe fbXxbSede nedinanalogytoX2xRAn:j.Then@sX@sfe K%֟x0S;,URliminf%̹n!1>^(Z̹mY̹m+1>:::$Y̹nR+:::+Z̹m+nɌ)UR=:Xfe xA0Am ;swhereL(Xfe  x0q)andL(Xfe x 0 m)areidenrtical.8Thisimplies@sX@sfe K%֟x0S;,=URXURfe xA0Am a.s.Bforallfp)mUR2N;si.e. X fe x0isFmeasurablewithrespSectto(thecompletionof8)thetail{ eldof0Ts(Y̹nP;Z̹n) n2N.9Thrus@X@fe  x0Y{@andsimilarlyfe fbX 0{arealmostsurelyconstanrt.9There-sforeitsucestoshorwthatXfe exxbxandfe fbXexareinfactindepSendenrtofx2R̸+x.sHeresupP̹n0* S̹n=UR+1marybSeassumed,becauseotherwise@sX xڍnX 0ڍn =URxe Sn!0a.s..3.8TVotreatthelorwerlimit rst,considertherandomtime@sT:=URinfHfnUR0:X 0ڍn xg;@6Q썠:-iӍ{-swhicrhis nitealmostsurelyby(1).8ThengJ@sX@sfe K%֟xx[pXpџfe {x0[pliminf_̹n!1(X 0ڍTY̹T.:+1}:::#H/Y̹T.:+n+:::+Z̹T.:+ne)[pliminf_̹n!1(xY̹T.:+1}:::#H/Y̹T.:+n+:::+Z̹T.:+ne)Zn=:pXpџfe x{x{T(;swhereZL(Xfe  xx)andL(Xfe x x TS)areidenrtical,bSecauseT: isastoppingtimewithsrespSectto(Y̹nP;Z̹n) n2N.8Thrus,indeed@sX@sfe K%֟xxS=URXURfe Ax0Ea.s.>forallc+ixUR2R̸+x:sThevcorrespSondingresultfortheupperlimitisanotherconsequenceof(1),swhicrhyieldsl򍍍@sfe fbXK%֟xSURfe fbXA0=UR1a.s., forallPd$x2R̸+x: 3Tq lasy102.The notationxfeRwand&feR]ڍxwillbSeusedinthesequelwithoutfurtherreference.sThe4inrtervXalde nedbytheselimitsattractsthesequence(X̹nP)̹n0Xinastrongssense:s(1.2)Prop`osition.Whenever! nite,thecffonstantsxfeR/and&feR]ڍxarffedeterminedsby35theeffquivalencess(a)xURxfeRif{4and35onlCynifGP(Ypx+Z1URx)=1;_s(b)xUR&feR]ڍxif{4and35onlCynifGP(Ypx+Z1URx)=1;smorffeover35the\if{pffart"holdswithoutthe nitenessassumption.sPrffoof.1.T Thebimplicationfromrighrttoleftisanimmediateconsequenceofs(1.1),bSecausee.g.8theassumption@sYpx+Z1URxa.s.sobrviouslyimplies@sfX̹n1URxgfX̹nxga.s. ;swhicrhinturnyields@sx@sfeRJv=URliminf%̹n!1>^X xڍn URinfF̹n0&X xڍnURx:.2. dTVoNprorvetheconverse,consider rstassertion(a). dFixanarbitrarysx20yh2]xfeRR;1[JandLletT̸1 k/<+T̸2::: K:denotethehittingtimesof[0;x209]brythessequencedY(X20RAn)̹n0%(bSeingde nedwithprobabilitry1). SinceT̹k#;k?R25N,aresstoppingtimeswithrespSectto(Y̹nP;Z̹n) n2N,therandomvXariables@s(Y p0ڍkj;Z ܞ0ڍk#)UR:=(Y̹Ti?kƸ+1Q;Z̹Ti?kƸ+1)for)ko2URN@7`썠:-iӍ{-sareagainindepSendenrtanddistributedaccordingto.8Therefore@sx@sfeRQ!9dvliminf>̹k6!1#X 0ڍTi?kƸ+1Q:!=dvliminf>̹k6!1#(Y̹Ti?kƸ+1QX 0ڍTi?k +Z̹Ti?kƸ+1)Q!9dvliminf>̹k6!1#(Y p0ڍkjx 0x+Z ܞ0ڍk#)Q!9dvyn9x 0x+zfor)(y;z)UR2N;sbSecauseZ(Y2p0RAkj;Z2ܞ0RAk#) k62N]visitseacrhneighbSorhoodZof(yn9;z)in nitelyoftenwithsprobabilitry1.8Lettingx20tendtoxfeRleadstos(1)xfeRURyn9xn9feR 3+zfor)(yn9;z)2N:sThisinequalitryholdsaswellwith0replacingxfeR ,hences(2)xURyn9x+zfor)(y;z)UR2N@and /xxfeR ;swhicrhisequivXalenttotheassertion@sxURYpx+Zܞa.s.,,for@xURxfeR :.3.%ThecorrespSondingprooffor&feR]ڍxrequiresonlyminorcrhanges:choosenowsx20#2UR[0;&feR]ڍxP[,whicrhispSossibleduetos(3)&feR]ڍxURlimsup)W̹n!1BZ̹n>UR0;sreplacetheinrtervXal[0;x209]by[x209;1[,anduse&feR]ڍx >UR0oncemoreforthepassagesbSetrween(thecounrterpartsof8)(1)and(2): 2.FVrom(1.2)itiseasilydeducedthatfor nitevXaluesxfeRand&feR]ڍx@sX̹n1/t^xfeR LURX̹nX̹n1_&feR]ڍxWa.s.5aforallYn2N:.NorwtheconstantsxfeRW0(see(3)intheproSofof(1.2))thisyieldsN̹e w=;. JSinces(yn9;z)UR=(1;0)canbSedisregarded,&feR]ڍxisthesmallestvXaluexsucrhthat@sxURxy+zfor)(yn9;z)2N̹c.y: 2.ItisatrivialconsequenceofthisresultthatX̹n !w1a.s.uwhenevrerN̹c-^issemptryV.cOtherwiseh)xh)feR}{h)unlike&feR]ڍx}{maydepSendonthedistribution)notonlysthroughitssuppSortN@.If,ehorwever,xfeR-Gresp.&feR]ڍxris nite,itcanbSeobtainedsgraphically: (0;xfeRP)Ϋresp. (0;&feR]ڍx)isthatpSoinrtwherethelowerresp. uppSerstangenrtfrom(1,0)toN̹cZintersectsthez{axis.2Thisimpliesinparticularthatsthein mrumorsupremumin(1.3)neednotbSeattained..InconrtrasttothepSossibilityX̹n!UR1a.s.,pconvergenceof(X̹nP)̹n0lwithinsR̸+ can~oSccuronlyinadegeneratecase,sevrenifweakenedtoconvergenceinsprobabilitry:s(1.4)Prop`osition.The35followingassertionsarffeequivalent:s(a)@wkx@wkfeRJz=UR n=&feR]ڍxwRith 0< <1;s(b)the*seffquence(X̹nP)̹n00convergesinprobabilitytoa nite{valuedrandomsvariable35X,s(c)?OYUR1andZ1= (1Yp) wRith0< n<1:sPrffoof.1.8Theimplication(a))(b)istrivial..2.Assumenorw(b)andletdbSeaboundedmetriconR̸+x.Then(yn9X̹n+az)̹n0sconrvergesinprobabilitrytoyn9X++z,hences(1)E(d(yn9X̹nR+z;yX++z))UR!0forall9Z(y;z)2R 2ڍ+x:sSinceX̹n and(Y̹n+1;Z̹n+1)areindepSendenrt,moreover@sqCRKE(d(yn9X̹nR+z;X̹nP))d=URE(d(X̹n+1;X̹n))UR!0:@9 y썠:-iӍ{-sThrusthereisasubsequence(X̹ni?k ?j)̹k60suchthat\cs(2)E(d(yn9X̹ni?k +z;X̹ni?k ?j))UR!0for){almostall<(yn9;z)2R 2ڍ+x:sWheny?comrbinedwiththerestrictionof(1)tothissubsequence,appliedtos(yn9;z)aswrellasto(1,0),(2)yields@sE(d(yn9X++z;X))UR=0for){almostall<(y;z)2R 2ڍ+x:sWithUR:=L(X)thisimplies@syn9x+zs[5=Wxfor){almostall<(y;z)UR2R 2ڍ+x;stherefore,bryFVubini,@syn9x+zQ0T5=Wxfor){almostall<xUR2R̸+x:sThrusthereexistsindeed n2URR̸+  suchthat@sZ1=UR (1Yp);swhere n6=UR0(sinceotherwiseZ1=0)andY1(bSecauseofZ10)..3.8Theimplication(c))(a)isimmediatefrom(1.2): 2.ClearlyV,)^theconstanrt isacommon xedpSointoftheunderlyinganesmapsalmostsurelyV.*s2.RecurrenceandtransiencesInviewofX̹nUR0the rstclassi cationisvrerynatural:s(2.1)De nition.Thedistribution^8(orthekernelPortheprffocess(X̹nP)̹n0)sis35cffalleds(a)\rffecurrent" ifxfeR<UR1,s(b)\trffansient" ifxfeR=UR1..Both}casescanbSedistinguishedaswrellbytheassoSciatedpotenrtialkernelsGUR:=CP㋟̹n0"hUPƟ2nJ,indepSendenrtlyoftheinitiallaw:s(2.2)Theorem.The35followingdichotomyholds:s(a)if35isrffecurrent,35then\c@sCPM ̹n0_P(X̹nURt)=1for)t>xfeR ;s(b)if35istrffansient,then@sCPM ̹n0_P(X̹nURt)<1for)t<1:sPrffoof.(a)Thisisanimmediateconsequenceof@sP(X̹nURtin nitelyoftenQ)=1:ݿB10 썠:-iӍ{-.(b)De nerecursivrelyp@sT̸0V:=UR0 and*,T̹kx:=infHfn>T̹k61U`:X̹ntg(1):sTheninparticular@s0UR=P 0(X̹ntin nitelyoftenQ)=lim ̹k6!1-ʬP 0(T̹kx<1);shencethereexistsl2URNsucrhthat@s#UR:=P 0(T̹lw<1)<1:sWiththedecreasingfunction@sgn9(x)UR:=P xH(T̹lw<1)sthisimplies@sP 0(T߸(k6+1)jlL<UR1)h=?ןqCRꀟߺfTi?kl<1ggn9(X̹Ti?kl r)dP 0?ןqCRꀟߺfTi?kl<1ggn9(0)dP 0h=?#P 0(T̹k6l <UR1):psTherefore@sP 0(T̹k6l <UR1)# k#forall>~(ko0;sandagainbrymonotonicitythisyields@sCPM ̹n0_P(X̹nURt)CߚCPmӟ̹n0P 0(X̹nURt)+=ߚE 0(jfnUR0:X̹ntgj)+=ߚCPmӟ̹i0ϯ'P 0(T̹i,<UR1)CߚlCP'̹k60"'&P 0(T̹k6l <UR1)CߚlCP'̹k60"'&# kx<UR1: 2p.Thenextresultisasimpleconsequenceof(2.2)(andneededbSeforeasstrongervrersionwillbSeavXailable):s(2.3)Prop`osition.is35rffecurrentwheneverP(Y=UR0)>0.sPrffoof.FVoranrytUR<1satisfying@sP(Y=UR0;Z1t)>0stheassertionfollorwsfrom(2.2a)inviewof@sCPM ̹n0_P(X̹nURt)CP㋟ n2N%JP(Y̹n=0;Z̹nt): 2.Equallysimpleisthefollorwingcounterpart:ݿB11 ,썠:-iӍ{-s(2.4)Prop`osition.is35trffansientwheneverS̹n!UR+1:sPrffoof.SinceH@sT:=URinfHfnUR2N:Z̹n>0gsde nesf5an(almostsurely nite)stoppingtimewithrespSectto(Z̹nP) n2N,brytheshrypSothesis@sS̹nRS̹T i!UR1a.s.sThrustheassertionisaconsequenceof@sX̹nURZ̹Te Sn7SX.T1m_forEv9nT: 2.ThatBtheconrverseBof(2.4)doSesnotholdingeneralcanbedemonstratedbrysasomewhatsurprisingresult.HorweversmalltheprimaryvXariableYp,inviewsof0(2.3)onlysuppSosedtobestrictlypositivre,Bmay0be,BthesecondaryvXariablesZcanC%bSemadelargeenoughfortransience,YDevrenifinadditionindependencesofYandZFispSostulated.8MorepreciselyV,intermsofdistributions:s(2.5)Prop`osition.ForC%any̹yR_2URM̸1(R̸+x)with̹y (f0g)=0and̹y (f1g)6=1stherffeGexists̹z 2URM̸1(R̸+x)with̹zʮ(f0g)6=1suchthat=̹yb e̹zistrffansient.sPrffoof.LetY̹nP;nUR2N,bSeindependenrtwithdistribution̹yandassumewithoutslossofgeneralitryY<UR1.8ThenchoSoseasequence(c̹nP)̹n0otsatisfyingHs(1)0UR"̸1V>"̸2>:::uD!0;s(4)b̹n:=URP(Y̸1:::Y̹n1"̹nP)2 nDc̸1:::c̹nPfor.*nUR2N;swhere.theassumptionP(YeX=0)=0.enrters.IndepSendentlyofY̹nP;n2N,?letsZ̹nP;nUR2N,bSeindependenrtwithadistribution̹zVsuchthat@sP(Z1=UR0)=c̸0andA0P(Z=1="̹n ')=c̹nRc̹n1for0n2N;shenceinparticular@sP(Z1UR1="̹n ')=c̹nPfor.*n2N:sWithKthedualsequence(W̹nP)̹n0,kde nedinSection0,considernorwtheevents@ A̹nY Y:=opmfW̹nUR1g;@sB̹nY Y:=opmfY̸1:::Y̹n1UR"̹nPg;@C̹nY Y:=opmfZ̹nUR1="̹n 'g;ݿB12 썠:-iӍ{-swhicrhobviouslysatisfy@sA̹nURA̹n1/t\(B̹nR[C̹nP)(A̹n1/t\C̹nP)[B̹nPfor.*n2N:sWiththenotationa̹n:=URP(A̹nP)thisyieldsbryindepSendencetheinequality@sa̹nURa̹n1c̹nR+b̹nPfor.*n2N;swhicrhbyinduction,using(4),leadsto@sa̹nUR(1+:::+2 n D)c̸1:::c̹nPfor.*n0:sBy(2),therefore@sCPM ̹n0_P(X 0ڍn UR1)N(=CPП̹n0ӝP(W̹nUR1)5@2CP8̹n0"hUc̸1:::c̹n<UR1:sAccordingWto(1.3a)thelorwerWlimitxfeR ,rduetoP(Y2<1;Z^=0)>0,canWonlystakrethevXalues0or1.Butthe rstpSossibilityisruledoutby(2.2a),/andsthrus=UR̹y ̹zVistransient: 2.The̢ nalresultofthissectionisaconsequenceofthemonotonicitryandswillbSecrucialinSections5and7:s(2.6)Lemma.If35fQ2URK,`(R̸+x),then@sfG(X̹nP)f(X xڍn:j)UR!0a.s.- for35allRYx2R̸+x:sPrffoof.1.ItsucestoprorvetheassertionunderthehrypSothesisX̸0V=URx̸02R̸+x,sbSecause`itsgeneralvXaliditrythenfollowsbyintegration.ComparingfG(X2xqAacmr60RAn e)sandKfG(X2xRAn:j)withf(X20RAn)shorwsthatinfactx̸0 n=0maybSeassumed. \Sincesthe6assertionisobrviouslytrueinthetransientcase,ImoreoverrecurrencewillsbSerassumedinthesequel.Accordingto(2.4)therandomwralk(S̹nP)̹n0kthenshits]theinrtervXal[1; ]in nitelyoftenwithprobability1,Jwhere ywillbSescrhosenWattheendoftheproSof.#IfT̸1V<URT̸2<:::vareWthecorrespSondinghittingstimes,therandomvXariables@s(Y p0ڍkj;Z ܞ0ڍk#)UR:=(Y̹Ti?kƸ+1Q;Z̹Ti?kƸ+1)for)ko2URNsareagainindepSendenrtanddistributedaccordingto..2.8Next,inviewof@s0UR0)=lim ̹m!10P(Y0:sTherefore,brypart1oftheproSof,therandomtime@sT:=URinfHfT̹kx:URY̹Ti?kƸ+1qT(!n9)obrviouslyr?@sX xڍn:j(!n9)X 0ڍn(!)UR=xCQ߸0ҀY̹m(!);swherethetrwoproSductsCQ\o̸1andCQ\o̸2canbSeestimatedbry@sCQK実̸1S=URe ST(!7)(!I{)%e ";m@sCQK実̸2SURlCZ߹T.:(!I{)+1(!n9)CQ߹T.:(!I{)+10,choSoseȄ>UR0suchthat@sjfG(t̸1)f(t̸2)jUR<"for)jt̸1jt̸2j<:sThisyields@sfG(X xڍn:j(!n9))f(X 0ڍn(!n9))UR=0for)X 0ڍn(!n9)>t;sinviewofX2xRAn:j(!n9)URX20RAn(!),and@sjfG(X xڍn:j(!n9))f(X 0ڍn(!n9))jUR<"for)X 0ڍn(!n9)t;sifinaddition@sjX xڍn:j(!n9)X 0ڍn(!)jUR<:sBy(1)thisconditionissatis edforxe2 lCtUR<s2,i.e.0if y4iscrhosensucientlyslarge: 2*s3.RecurrencecriteriasThesucienrtconditionsforrecurrenceandtransience,#givenin(2.3)and(2.4),sapply6onlytoextremecases.TVodealwithconcretesituationsstrongercriteriasareJnecessaryV.SThe rstrelevXanrtresultconcernsessentiallytheadditivemoSdel.sAslighrtgeneralizationyields:s(3.1)Theorem.For350UR< n<1thefollowingdichotomyholds:s(a)is35trffansient,if5@sYUR andliminf7̹t!1N0tP(log-IZ1>t)>logō%|1ΟQmfeX  Y;ݿB14ՠ썠:-iӍ{-s(b)is35rffecurrent,if-ҍ@sYUR andlimsup;b̹t!1R>tP(log-IZ1>t)URs+t)>logō%|1ΟQmfeX  2YforallWs0;9swhicrhfor xedsimpliestheexistenceof h>UR1andl2Nsucrhthat&@smlogōz1 "QmfeX  P(log-IZ1>URs+mlogō(1`zQmfeX  S) logō1t QmfeX  1fforEonmlC:sTherefore,bryindepSendence,܍@sP(X̹nURe sn<)enP(CT US̹lKmlC;nswherethelastinequalitrymakesuseof hUR1,implying@s(1x) JUR1 xfor)0x1:sSummationorvernyields@sCPM ̹n0_P(X̹nURe sn<)(l7+1)+(l1) ?CP.x̹nlō+u1'Qmfe  n 9t<UR1;sandthetransiencefollorwsfrom(2.2a),bSecausesisarbitraryV..(b)}PAgain,.Y=UR $lmarybSeassumed.mInadditionZYmaybSereplacedby0onstheLsetfZwzgfor xedz#b<1,ubSecausethisisirrelevXanrtforthehypSothesissand4crhangesthevXaluesofX̹n byz=(1 )4atmost.2dByanappropriatechoicesof <z1andzf<1,therefore,thefollorwingconditionscanbSesatis ed(insthegivrenorder):-ҍs(1)tP(log-IZ1>URt) logō1tQmfeX  3fforallW(t0; q񍍍s(2)P(Z1=UR0)Ȅ:=  1 y/:E%sWiththeabbreviation-ҍ@sm̹n:=URlogn=logō(1`zQmfeX  +2for)nUR2NݿB15]썠:-iӍ{-sthisyieldsbryindepSendence>@sP(X 0ڍn UR1)"=wP(CT US̸0mUR[mlogō(1`zQmfeX  logn]))%jZm CQylП̹mn7m̹n thedi erence[:::ʞ]satis estheconditions?ꍍ@s[::: ʠ]UR>0 and*, logō1t QmfeX  f=[:::]UR1:KڍsTheestimationofCQ\o̸2canbSeconrtinuedby@sCQK実̸2Zm CQylП̹mn70.s|IftP(log-IZiy>t)!1,qthenthesequence(X̹nP)̹n0&{istransienrtwheneversY=UR n>0;iftP(log-IZ1>URt)!0,thenitisrecurrenrtwheneverY=UR n<1..Therestofthissectionisdevrotedtorecurrencecriteriaforthecasethatthesunderlyinganemapsarenotnecessarilyconrtractions.aHerethepSossibilitysS̹n (!l+1%Gisruledoutbry(2.4),si.e.inf ̹n0+|S̹n=l1hastobSeassumed.ݿB16Τ썠:-iӍ{-sThenEQthefollorwingauxiliaryresultcanbSeobtainedbyapartitionintorandomsbloScrks:s(3.2)Lemma.Ifinfџ̹n0)S̹n=UR1and@sE(X 0ڍT)UR<1 fGor ST:=infHfn2N:S̹n<0g;sthen35isrffecurrent.sPrffoof.1.Inviewof(2.3)thehrypSothesisP(YF=0)=0canbeusedinthessequel.SetT̸0Q:=|0andletT3B=T̸1Q̹k6!1#E(X 0ڍk#)Q:!=dvliminf>̹k6!1#(s2  k61Q+:::+)Q:!=dvs0=(1 )UR<1: 2.NorwthetwomainrecurrencecriteriacanbSederivedsimultaneously:s(3.3)Theorem.If Uinf!I̹n0,S̹n :=1,bthenisrffecurrentineffachofthesfollowing35cffases:s(a)@wkE(Z1jURYp) fGorsome35 n<1;!Qns(b)AP(Y=UR0)=0andEf`Cōo3Z,Qmfe m  Yf`C*<UR1:ݿB17܌썠:-iӍ{-sPrffoof.1.{InV2viewof(2.3)thehrypSothesisP(Y= ^0)=0V2canbeusedinbothscases.ԝMoreorver,the:::$Y̹nP)X=ؕSE(E(:::jURY̸1;:::ʜ;Y̹nP))X=ؕSE(1ߺfT.:=ngY̹m+1>:::$Y̹nRE(Z̹m ZjURY̹m))?ؕSE(1ߺfT.:=ngY̹m+1>:::$Y̹nP)for)1URmn;swherethelastequationusesthatfTv="ngismeasurablewithrespSecttosY̸1;:::ʜ;Y̹n and9(Y̹m;Z̹m)9isindepSendenrtofY̹l!;ls6=m.&InviewofY̸1:::Y̹n 41sonfT=URngthisyields@sE(X 0ڍT)lL=*CP n2N]CP̸1mnϑE(1ߺfT.:=ngZ̹mY̹m+1>:::$Y̹nP)ld*CP m2N'CPH`̹n>mE(1ߺfT.:=ngY̹m+1>:::$Y̹nP)+1Սld*CP m2N'CPH`̹n>mE(1ߺfT.:=ngō1Qmfe >  Y̸1*݉:::ō@V[1;ZQmfe  Y̹mK)+1$lL=*CP̹m02E(1ߺfT.:>mgō!N/1uQmfe >  Y̸1-9:::ōB1>7ΟQmfe  Y̹mN@);Hswhere8cthesummand1stands rstforCPƜ n2N%k[E(1ߺfT.:=ng)andthenforE(1ߺfT.:>0g).sThe nalresultcanbSerewrittenass(1)E(X 0ڍT)URE(CP 9̸0m  Y̸1*݉:::ōEę1;ZQmfez  Y̹m1ōW:Z̹mW:Qmfe  Y̹mi7)&.ЍlL=*CP m2N'E(1ߺfT.:>m1gō,*1)R Qmfe >  Y̸18y:::ōR1IJQmfez  Y̹m1c)Ef`Cō,Z̹m,Qmfe  Y̹mnf`C%Xld*CP̹m02E(1ߺfT.:>mgō!N/1uQmfe >  Y̸1-9:::ōB1>7ΟQmfe  Y̹mN@);HswherethelastequationusesthatfT) >Dm1gismeasurablewithrespSecttosY̸1;:::ʜ;Y̹m1andZ̹m=Y̹m lisindepSendenrtofY̸1;:::ʜ;Y̹m1@..4.SNorw$theproSofcanbejoinrtlycompleted.STheessentialtoSolisSpitzer'ssidenrtityV,whichswillbSeappliedinitsrealform(seee.g.[28],p.395).LettingstheretUR"1leadstooōs(2)E(CP 9̸0m0.sPrffoof.BothJOassertionsareimmediateconsequencesoftheircounrterpartsins(3.3): 2 sReferences""K`y 3 cmr101.0sAlpuim,:M.:dAnextremalMark!oviansequence.xJ.Appl.Prob.'"V 3 cmbx1026,:219{2320s(1989)"2.0sBarnsleye,cM.,Elton,J.: A=new=classofMark!ov=proMcessesforimageencoding.0sAdv.Appl.Prob.20,f14{32(1988)"3.0sBarnsleye,>M.,Elton,J.,Hardin,D.:6Recurren!titeratedfunctionsystems.Con-0sstr.Appro!x.5,f3{31(1989)"4.0sBoro!vkov,WA.:tOntheergoMdicit!yandstabilityofthesequence# b> 3 cmmi10wzn+1s= f-(wznP;1zn).0sTheoryfProb.Appl.33,595{611(1989)"9.0sDubins,+L.,Fereedman,D.:In!vdDariantvprobabilitiesforcertainMark!ovvproMcesses.0sAnn.Math.Stat.37,f837{848(1966)ݿB19썠:-iӍ{- 10.0sElton,_1J.:An:A.:On2Fthecon!tinuity2FofthedistributionofasumofdepMenden!t0svdDariablesconnectedwithindepMenden!twalksonlines.TheoryProb.Appl.19,0s163{168f(1974) 25.0sLampMerti,J.:mCriteriafortherecurrenceortransienceofstoc!hasticprocessesI.0sJ.fMath.Anal.Appl.1,314{330(1960) 26.0sLampMerti,J.:6Criteriaforstoc!hasticprocessesII:passage{timemomen!ts.bJ.0sMath.Anal.Appl.7,f127{145(1963) 27.0sLev,w9G.:ŗSemi{Mark!ovCproMcessesofm!ultiplicationwithdrift. 9tTheoryProb.0sAppl.17,f159{164(1972) 28.0sLo"Dev!e,M.:6ProbabilityRtheoryI,4thedition. -NewYeork{HeidelbMerg{Berlin:0sSpringerf1977 29.0sMasimo!v,4V.:gAUgeneralizedyBernoullischemeanditslimitdistribution.9Theory0sProb.Appl.18,f521{530(1973) 30.0sMukherjea,eA.:vRecurren!t2randomwalkinnonnegativematrices:vattractorsof0scertainEiteratedfunctionsystems.zProb.TheoryERelatedFields91,|297{3060s(1992) 33.0sNummelin,xE.:ߓGeneralAirreducibleMark!ovAchainsandnon{negativeopMerators.0sCam!bridge:UniversityfPress1984 34.0sRac!hev,tS.,SamoroMdnitskye,G.:iLimitg}lawsforastoMchasticproMcessandrandom0srecursionfarisinginprobabilit!ymoMdelling.Preprint(1992) 35.0sRevuz,3tD.:Mark!ovchains,2ndedition.Amsterdam{NewYeork:North{Holland0s1984 36.0sRos"Den,sB.:&OnJtheasymptoticdistributionofsumsofindepMenden!tidentically0sdistributedfrandomvdDariables.Ark.Mat.4,f323{332(1961) 37.0sRosen!blatt,fM.: 3 cmmi10"K`y 3 cmr10t : cmbx9K cmsy82cmmi8 |{Ycmr8q% cmsy6;cmmi6Aacmr6