Critical Random Walk in Random Environment on Tree

arXiv:math/0404049v1[math.PR]2Apr2004CRITICALRANDOMWALKINRANDOMENVIRONMENTONTREESOFEXPONENTIALGROWTHROBINPEMANTLE12ABSTRACT:ThispaperstudiesthebehaviorofRWREontreesinthecriticalcaseleftopeninpreviouswork.Fortreesofexponentialgrowth,arandomperturbationofthetransitionprobabilitiescanchangeatransientrandomwalkintoarecurrentone.Thisistheoppositeofwhatoccursontreesofsub-exponentialgrowth.1IntroductionThispaperisconcernedwiththeproblemofdeterminingwhetheraran-domwalkinarandomenvironment(RWRE)onaninfinite,exponentiallygrowingtreeistransientorrecurrent.Theproblemwasfirststudiedin[8]asawayofanalyzinganotherprocesscalledReinforcedRandomWalk,andthenin[7]whereamorecompletesolutionwasobtained.ItwasshowntherethattheRWREistransientwhenthesizeofthetree,asmeasuredbythelogofthebranchingnumber,isgreaterthanthebackwardpushoftherandomenvironment,andrecurrentwhenthelogofthebranchingnumberissmallerthanthebackwardpush.Thecaseofequalitywasleftopen.Fortreesofsub-exponentialgrowth,thiscriticalcasewasalmostcompletelysettledin[9].Thepresentpaperisacompanionto[9]inthatitattemptstosettlethecriticalcaseforexponentiallygrowingtrees.Theresultsherearelessdefinitivethaninthesub-exponentialcase,inthatthesufficient1ResearchsupportedinpartbyaNationalScienceFoundationpostdoctoralfellowshipandbeNSFgrant#DMS91037382DepartmentofMathematics,UniversityofWisconsin-Madison,VanVleckHall,480LincolnDrive,Madison,WI53706conditionsfortransienceandforrecurrenceareintermsofcapacityandgrowthrespectively;theseconditionsarenotquitecomplementary,leavingopenacritical-within-criticalcase.Atechnicalassumptionontheran-domenvironmentisalsorequired;examplesshowthatthisassumptionisoftensatisfied.Onthepositiveside,itisprovedherethataphasebound-aryoccursinanunusualplace,namelywhenthegrowthrateofthetree,exp(βn+o(n)),hastheo(n)termequaltoaconstanttimesn1/3.Herefollowsaprecisedescriptionoftheproblem.LetΓbeanyinfinite,locallyfinitetreewithnoleaves(verticesofdegreeone).DesignateavertexρofΓasitsroot.Foranyvertexσ6=ρ,denotebyσ′theuniqueneighborofσclosertoρ(σ′isalsocalledtheparentofσ).Anenvironmentforrandomwalkonafixedtree,Γ,isachoiceoftransitionprobabilitiesq(σ,τ)ontheverticesofΓwithq(σ,τ)0ifandonlyifσandτareneighbors.Whenthesetransitionprobabilitiesaretakenasrandomvariables,theresultingmixtureofMarkovchainsiscalledRandomWalkinRandomEnvironment(RWRE).Following[7]andthereferencestherein,randomenvironmentsstudiedinthispapersatisfythehomogeneityconditionThevariablesX(σ)=lnq(σ′,σ)q(σ′,σ′′)arei.i.d.for|σ|≥2,(1)where|σ|denotesthedistancefromσtoρ.Here,andthroughout,letXdenotearandomvariablewiththiscommondistribution.Beforestatingthemainresult,afewdefinitionsandnotationsarere-quired.Writeσ≤τifσisonthepathconnectingρandτ;inthispaper,theterm“path”alwaysreferstoapathwithoutself-intersection.Writeσ∧τforthegreatestlowerboundofσandτ;pictorially,thisiswherethepathsfromρtoσandτdiverge.Let∂Γ,calledtheboundaryofΓ,denotethesetofinfinitepathsbeginningatρ.LetΓndenotetheset{σ:|σ|=n}ofver-ticesatlevelnofΓ.Definethebackwardpushoftherandomenvironment,denotedβorβ(X),byβ(X)=−lnmin0≤λ≤1EeλX.Thesizeofaninfinitetreeisbestdiscussedintermsofcapacity.Definition1Letφ:Z+→R+beanonincreasingfunction.Definetheφ-energyofaprobabilitymeasureμontheboundaryofΓtobeIφ(μ)=Z∂ΓZ∂Γφ(|ξ∧η|)−1dμ(ξ)dμ(η).DefinethecapacityofΓingaugeφbyCapφ(Γ)=infμIφ(μ),wheretheinfimumisoverallprobabilitymeasureson∂Γ.,andCapφ(Γ)6=0ifandonlyifthereissomemeasureoffiniteenergy.SaythatΓissphericallysymmetricifthereisagrowthfunctionf:Z+→Z+suchthateveryvertexσ6=ρhas1+f(|σ|)neighbors;inotherwords,thedegreeofavertexdependsonlyonitsdistancefromtheroot.AsphericallysymmetrictreeΓhaspositivecapacityingaugeφifandonlyifXφ(n)|Γn|−1∞.Thuspositivecapacityingaugeφ(n)=e−knimpliesliminfexponentialgrowthrateofatleastk.Inparticular,thesupremumofthosekforwhichΓhaspositivecapacityingaugeφ(n)=e−knistheHausdorffdimension,dim(Γ);intheterminologyof[5]and[7],dim(Γ)isthelogofthebranchingnumber.Themainresultof[7]isthatRWREonΓisa.s.transientifdim(Γ)β(X),anda.s.recurrentifdim(Γ)β(X).Theuseofgaugesmoregeneralthane−knallowsforfinerdistinctionsofsizetobemadewithintheclassoftreesofthesamedimension.Inparticular,whenβ=dim(Γ)=0,itisshownin[9]thatpositivecapacityingaugen1/2issufficientandalmostnecessaryfortransienceofRWRE.Sincethecaseβ=0isinsomesenseamean-zeroperturbationofthedeterministicenvironmentofasimplerandomwalk(X≡0),andsimplerandomwalkistransientifandonlyifΓhaspositivecapacityingaugen−1,thisshowsthattheperturbationmakesthewalkmoretransient.Bycontrast,themainresultofthispaperisasfollows.Definition2SaythatarealrandomvariableXistop-heavyiftheinfi-mumofEeλXoverλ∈[0,1]isachievedatsomeλ0∈(0,1)andEeγX∞forsomeγλ0.Theorem1ConsiderRWREonatreeΓwithβ(X)=dim(Γ)0.IfX=−βwithprobabilityone,thenRWREistransientifandonlyifΓhaspositivecapacityingaugeφ(n)=e−nβ.OntheotherhandifXisnondeterministic,top-heavy,andiseitheralatticedistributionorhasanabsolutelycontinuouscomponentwithdensityboundedaboveandboundedawayfromzeroinaneighborhoodofzero,then(i)thereexistsc1(X)forwhichthegrowthbound|Γn|≤eβn+c1n1/3forallnimpliesthatR