Asymptotic behavior of edge-reinforced random walk

arXiv:math/0511750v2[math.PR]27Mar2007TheAnnalsofProbability2007,Vol.35,No.1,115–140DOI:10.1214/009117906000000674cInstituteofMathematicalStatistics,2007ASYMPTOTICBEHAVIOROFEDGE-REINFORCEDRANDOMWALKSByFranzMerklandSilkeW.W.RollesUniversityofMunichandTechnischeUniversit¨atM¨unchenInthisarticle,westudylinearlyedge-reinforcedrandomwalkongeneralmulti-levelladdersforlargeinitialedgeweights.Forinfiniteladders,weshowthattheprocesscanberepresentedasarandomwalkinarandomenvironment,givenbyrandomweightsontheedges.Theedgeweightsdecayexponentiallyinspace.Theprocessconvergestoastationaryprocess.Weprovideasymptoticboundsfortherangeoftherandomwalkeruptoagiventime,showingthatitlocalizesmuchmorethananordinaryrandomwalker.Therandomenviron-mentisdescribedintermsofaninfinite-volumeGibbsmeasure.1.Introduction.Edge-reinforcedrandomwalkonalocallyfiniteundi-rectedgraphisthefollowingprocess:Everyedgeisassignedaweightwhichchangeswithtime.Initially,allweightsequalaconstanta.Therandomwalkerstartsatavertex0.Ateverytime,therandomwalkerjumpstoaneighboringvertexwithprobabilityproportionaltotheweightofthetra-versededgeatthattime.Eachtimeanedgeistraversed,itsweightisin-creasedby1.ThismodelwasintroducedbyDiaconisin[1]and[2].Theprocessispar-tiallyexchangeable.Alreadyin1980,DiaconisandFreedman[3]provedforthemoregeneralclassofpartiallyexchangeableprocessesarepresentationasamixtureofMarkovchains,providedtheprocessisrecurrent.Inthelate1980s,Diaconisaskedwhetheredge-reinforcedrandomwalkonZdisrecurrent.Exceptford=1,thisproblemisstillunsolved.Onaninfinitebinarytree,Pemantle[8]showedaphasetransitionintherecurrenceandtransiencebehaviorofedge-reinforcedrandomwalk.Forgeneralfinitegraphs,CoppersmithandDiaconis[1]foundanexplicitdescriptionforthelimitingfractionoftimespentattheedges.TheirresultwasextendedbyReceivedNovember2004;revisedNovember2005.AMS2000subjectclassifications.Primary82B41;secondary60K35,60K37.Keywordsandphrases.Reinforcedrandomwalk,convergencetoequilibrium,randomenvironment,Gibbsmeasure.ThisisanelectronicreprintoftheoriginalarticlepublishedbytheInstituteofMathematicalStatisticsinTheAnnalsofProbability,2007,Vol.35,No.1,115–140.Thisreprintdiffersfromtheoriginalinpaginationandtypographicdetail.12F.MERKLANDS.W.W.ROLLESKeaneandRolles[6].In[9],RollesshowedthataclassofmodelscanberepresentedasamixtureofreversibleMarkovchains.Thisresultappliesinparticulartoedge-reinforcedrandomwalkonanyfinitegraph.Edge-reinforcedrandomwalkswereusedin[4]toprovidenaturalBayesianpriorsforreversibleMarkovchains.In[7],weprovedthattheedge-reinforcedrandomwalkontheladderZ×{1,2}isrecurrentforallinitialedgeweightsa3/4.Thisresultwasgeneralizedbyoneoftheauthorsin[10]tographsofthetypeZ×GandN0×G,whereGisafinitetree,providedthattheinitialweightsaresufficientlylarge.Inthisarticle,weexaminetheasymptoticbehavioroftheseedge-reinforcedrandomwalksontheinfiniteladderN0×Ginmuchmoredetailbeyondre-currence.Formaldescriptionofthemodelandnotation.Weconsideredge-reinforcedrandomwalkonagraphG=(V,E).ThevertexsetVisofthetypeV=N0×VwithafinitesetV,|V|≥2.ThesetVisassumedtobethevertexsetofafinitetreeG=(V,E).Twovertices(i,v),(i′,v′)∈Varecon-nectedbyanedgeinEiffi=i′andv,v′areconnectedbyanedgeinE,or|i−i′|=1andv=v′.TheedgesofGareundirected.Theedge-reinforcedrandomwalkerstartsatlevel0ofG,thatis,inavertex0=(0,v).Furthermore,weassumetheinitialweightsatobesufficientlylarge.Morequantitatively,weassumeaamin,whereamin=3/4ifV={1,2},andotherwiseamin=amin(G)denotesthelowerboundspecifiedinformula(1.7)of[10].Optimizingthelowerboundforaisnottreatedinthispaper.Theedge-reinforcedrandomwalkonGisformallydefinedasfollows:LetXt:VN0→Vdenotethecanonicalprojectiononthetthcoordinate;Xtisinterpretedasthelocationoftherandomwalkerattimet.Fort∈N0,wedefinewt(e):VN0→R+,theweightofedgeeattimet,recursivelyasfollows:w0(e):=aforalle∈E,(1.1)wt+1(e):=wt(e)+1,fore={Xt,Xt+1}∈E,wt(e),fore∈E\{{Xt,Xt+1}}.(1.2)ThedistributionP0oftheedge-reinforcedrandomwalkisaprobabilitymeasureonVN0,definedbyX0=0,P0-a.s.,(1.3)P0[Xt+1=v|Xi,i=0,1,...,t]=wt({Xt,v})P{e∈E:Xt∈e}wt(e),if{Xt,v}∈E,0,otherwise.(1.4)Foravertex(i,v)∈V,weset|(i,v)|:=|i|,andweabbreviatevi:=(i,v).Ife={u,v}isanedgeinthefinitegraphG,wesetei:={ui,vi}.ForanASYMPTOTICBEHAVIOROFERRW3edgee={u,v}∈E,wedenoteby|e|itsdistancefromlevel0:weset|e|:=min{|u|,|v|}.Constantsaredenotedbyci,i≥1.Theykeeptheirmeaningthroughoutthewholearticle.2.Results.2.1.Positionoftherandomwalkeratlargetimes.Typically,attimet,simplerandomwalkislocatedatadistanceoftheorder√tfromitsstartingpoint.Incontrasttothisfact,thetypicallocationofedge-reinforcedrandomwalkattimetdoesnotgotoinfinityastgrows.Infact,thelocationofthereinforcedrandomwalkattimetisstochasticallyboundedbyarandomvariablewithexponentialtails,uniformlyforalltimest.Thisistheclaimofthefollowingtheorem:Theorem2.1(Uniformexponentialtailsforthelocationoftherandomwalk).Thereexistconstantsc1,c20,dependingonlyonGanda,suchthatforallt,n∈N0,thefollowingboundholds:P0(|Xt|≥n)≤c1e−c2n.(2.1)Asaconsequence,uptotimet,theedge-reinforcedrandomwalkcantravelatmostadistanceoftheorderlnt:Corollary2.2(Rangeof