suceswww.qqq147.com

SUBTREEPRUNEANDRE-GRAFT:AREVERSIBLEREALTREEVALUEDMARKOVPROCESSSTEVENN.
EVANSANDANITAWINTERAbstract.
WeuseDirichletformmethodstoconstructandanalyzeareversibleMarkovprocess,thestationarydistributionofwhichistheBrowniancontinuumrandomtree.
Thisprocessisinspiredbythesub-treepruneandre-graft(SPR)Markovchainsthatappearinphylogeneticanalysis.
AkeytechnicalingredientinthisworkistheuseofanovelGromov–Hausdortypedistancetometrizethespacewhoseelementsarecom-pactrealtreesequippedwithaprobabilitymeasure.
Also,theinvesti-gationoftheDirichletformhingesonanewpathdecompositionoftheBrownianexcursion.
Shorttitle:Subtreepruneandre-graft1.
IntroductionMarkovchainsthatmovethroughaspaceofnitetreesareanimpor-tantingredientforseveralalgorithmsinphylogeneticanalysis,particularlyinMarkovchainMonteCarloalgorithmsforsimulatingdistributionsonspacesoftreesinBayesiantreereconstructionandinsimulatedannealingalgo-rithmsinmaximumlikelihoodandmaximumparsimony1treereconstruction(see,forexample,[Fel03]foracomprehensiveoverviewoftheeld).
Usually,suchchainsarebasedonasetofsimplerearrangementsthattransformatreeintoa"neighboring"tree.
Onewidelyusedsetofmovesisthenearestneigh-borinterchanges(NNI)(see,forexample,[Fel03,BRST02,BHV01,AS01]).
Twootherstandardsetsofmovesthatareimplementedinseveralphyloge-neticsoftwarepackagesbutseemtohavereceivedlesstheoreticalattentionarethesubtreepruneandre-graft(SPR)movesandthetreebisectionandre-connection(TBR)movesthatwererstdescribedin[SO90]andarefurtherdiscussedin[Fel03,AS01,SS03].
WenotethatanNNImoveisaparticularDate:August10,2005.
2000MathematicsSubjectClassication.
Primary:60J25,60J75;Secondary:92B10.
Keywordsandphrases.
Dirichletform,continuumrandomtree,Brownianexcursion,phylogenetictree,MarkovchainMonteCarlo,simulatedannealing,pathdecomposition,excursiontheory,Gromov-Hausdormetric,Prohorovmetric.
SNEsupportedinpartbyNSFgrantsDMS-0071468andDMS-0405778.
1Maximumparsimonytreereconstructionisbasedonndingthephylogenetictreeandinferredancestralstatesthatminimizethetotalnumberofobligatoryinferredsubstitutioneventsontheedgesofthetree.
12STEVENN.
EVANSANDANITAWINTERtypeofSPRmoveandthatanSPRmoveisparticulartypeofTBRmove,and,moreover,thateveryTBRoperationiseitherasingleSPRmoveorthecompositionoftwosuchmoves(see,forexample,Section2.
6of[SS03]).
Chainsbasedonothermovesareinvestigatedin[DH02,Ald00,Sch02].
InanSPRmove,abinarytreeT(thatis,atreeinwhichallnon-leafverticeshavedegreethree)iscut"inthemiddleofanedge"togivetwosubtrees,sayTIandTP.
AnotheredgeischoseninTI,anewvertexiscreated"inthemiddle"ofthatedge,andthecutedgeinTPisattachedtothisnewvertex.
Lastly,the"pendant"cutedgeinTIisremovedalongwiththevertexitwasattachedtoinordertoproduceanewbinarytreethathasthesamenumberofverticesasT.
Figure1.
AnSPRmove.
Thedashedsubtreetreeattachedtovertexxinthetoptreeisre-attachedatanewvertexythatisinsertedintotheedgepb,cqinthebottomtreetomaketwoedgespb,yqandpy,cq.
Thetwoedgespa,xqandpb,xqinthetoptreearemergedintoasingleedgepa,bqinthebottomtree.
Asremarkedin[AS01],SUBTREEPRUNEANDRE-GRAFT3TheSPRoperationisofparticularinterestasitcanbeusedtomodelbiologicalprocessessuchashorizontalgenetrans-fer2andrecombination.
Section2.
7of[SS03]providesmorebackgroundonthispointaswellasacommentontheroleofSPRmovesinthetwophenomenaoflineagesortingandgeneduplicationandloss.
Inthispaperweinvestigatetheasymptoticsofthesimplestpossibletree-valuedMarkovchainbasedontheSPRmoves,namelythechaininwhichthetwoedgesthatarechosenforcuttingandforre-attachingarechosenuniformly(withoutreplacement)fromtheedgesinthecurrenttree.
Intu-itively,thecontinuoustimeMarkovprocesswediscussarisesaslimitwhenthenumberofverticesinthetreegoestoinnity,theedgelengthsarere-scaledbyaconstantfactorsothatinitialtreeconvergesinasuitablesensetoacontinuousanalogueofacombinatorialtree(morespecically,acom-pactrealtree),andthetimescaleoftheMarkovchainisspedupbyanappropriatefactor.
Wedonot,infact,provesuchalimittheorem.
Rather,weuseDirichletformtechniquestoestablishtheexistenceofaprocessthathasthedynamicsonewouldexpectfromsuchalimit.
Unfortunately,althoughDirichletformtechniquesprovidepowerfultoolsforconstructingandanalyzingsymmetricMarkovprocesses,theyarenotoriouslyinadequateforprovingconvergencetheorems(asopposedtogeneratorormartingaleproblemcharacterizationsofMarkovprocesses,forexample).
Wethereforeleavetheproblemofestab-lishingalimittheoremtofutureresearch.
TheMarkovprocessweconstructisapurejumpprocessthatisreversiblewithrespecttothedistributionofAldous'scontinuumrandomtree(thatis,therandomtreewhicharisesasthere-scalinglimitofuniformrandomtreeswithnverticeswhennVandwhichisalso,uptoaconstantscalingfactor,therandomtreeassociatednaturallywiththestandardBrownianexcursion–seeSection4formoredetailsaboutthecontinuumrandomtree,itsconnectionwithBrownianexcursion,andreferencestotheliterature).
Somewhatmoreprecisely,butstillratherinformally,theprocesswecon-structhasthefollowingdescription.
Tobeginwith,Aldous'scontinuumrandomtreehastwonaturalmea-suresonitthatcanbothbethoughtofasarisingfromthemeasureonanapproximatingnitetreewithnverticesthatplacesaunitmassateachvertex.
Ifwere-scalethemassofthismeasuretogetaprobabilitymeasure,theninthelimitweobtainaprobabilitymeasureonthecontinuumrandomtreethathappenstoassignallofitsmasstotheleaveswithprobabilityone.
Wecallthisprobabilitymeasuretheweightonthecontinuumtree.
Ontheotherhand,wecanalsore-scalethemeasurethatplacesaunitmassateachvertextoobtaininthelimitaσ-nitemeasureonthecontinuum2Horizontalgenetransferisthetransferofgeneticmaterialfromonespeciestoanother.
Itisaparticularlycommonphenomenonamongbacteria.
4STEVENN.
EVANSANDANITAWINTERtreethatrestrictstoone-dimensionalLebesguemeasureifwerestricttoanypaththroughthecontinuumtree.
Wecallthisσ-nitemeasurethelength.
Thecontinuumrandomtreeisarandomcompactrealtreeofthesortinvestigatedin[EPW04](wedenerealtreesanddiscusssomeoftheirpropertiesinSection2).
Anycompactrealtreehasananalogueofthelengthmeasureonit,butingeneralthereisnocanonicalanalogueoftheweightmeasure.
Consequently,theprocessweconstructhasasitsstatespacethesetofpairspT,νq,whereTisacompactrealtreeandνisaprobabilitymeasureonT.
LetbethelengthmeasureassociatedwithT.
OurprocessjumpsawayfromTbyrstchoosingapairofpointspu,vqTTaccordingtotheratemeasureνandthentransformingTintoanewtreebycuttingothesubtreerootedatuthatdoesnotcontainvandre-attachingthissubtreeatv.
Thisjumpkernel(whichtypicallyhasinnitetotalmass–sothatjumpsareoccurringonadensecountableset)ispreciselywhatonewouldexpectforalimit(asthenumberofverticesgoestoinnity)oftheparticularSPRMarkovchainonnitetreesdescribedaboveinwhichtheedgesforcuttingandre-attachmentarechosenuniformlyateachstage.
TheframeworkofDirichletformsallowsustotranslatethisdescriptionintorigorousmathematics.
Animportantpreliminarystepthatweaccom-plishinSection2istoshowthatitispossibletoequipthespaceofpairsofcompactrealtreesandtheiraccompanyingweightswithaniceGromov–Hausdorlikemetricthatmakesthisspacecompleteandseparable.
WenotethataGromov–Hausdorlikemetriconmoregeneralmetricspacesequippedwithmeasureswasintroducedin[Stu04].
ThelattermetricisbasedontheWassersteinL2distancebetweenmeasures,whereasoursisbasedontheProhorovdistance.
Moreover,weneedtounderstandindetailtheDirichletformarisingfromthecombinationofthejumpkernelwiththecontinuumrandomtreedistributionasareferencemeasure,andweaccom-plishthisinSections5and6,whereweestablishtherelevantfactsfromwhatappearstobeanovelpathdecompositionofthestandardBrownianexcursion.
WeconstructtheDirichletformandtheresultingprocessinSec-tion7.
WeusepotentialtheoryforDirichletformstoshowinSection8thatfromalmostallstartingpoints(withrespecttothecontinuumrandomtreereferencemeasure)ourprocessdoesnothitthetrivialtreeconsistingofasinglepoint.
WeremarkthatexcursionpathvaluedMarkovprocessesthatarere-versiblewithrespecttothedistributionofstandardBrownianexcursionandhavecontinuoussamplepathshavebeeninvestigatedin[Zam03,Zam02,Zam01],andthattheseprocessescanalsobethoughtofasrealtreevalueddiusionprocessesthatarereversiblewithrespecttothedistributionofthecontinuumrandomtree.
However,weareunawareofadescriptioninwhichtheselatterprocessesariseaslimitsofnaturalprocessesonspacesofnitetrees.
SUBTREEPRUNEANDRE-GRAFT52.
WeightedR-treesAmetricspacepX,dqisarealtree(R-tree)ifitsatisesthefollowingaxioms.
Axiom0(Completeness)ThespacepX,dqiscomplete.
Axiom1(Uniquegeodesics)Forallx,yXthereexistsauniqueisometricembeddingφx,y:r0,dpx,yqsXsuchthatφx,yp0qxandφx,ypdpx,yqqy.
Axiom2(Loop-free)Foreveryinjectivecontinuousmapψ:r0,1sXonehasψpr0,1sqφψp0q,ψp1qpr0,dpψp0q,ψp1qqsq.
Axiom1sayssimplythatthereisaunique"unitspeed"pathbetweenanytwopoints,whereasAxiom2impliesthattheimageofanyinjectivepathconnectingtwopointscoincideswiththeimageoftheuniqueunitspeedpath,sothatitcanbere-parameterizedtobecometheunitspeedpath.
Thus,Axiom1issatisedbymanyotherspacessuchasRdwiththeusualmetric,whereasAxiom2expressesthepropertyof"treeness"andisonlysatisedbyRdwhend1.
Wereferthereaderto([Dre84,DT96,DMT96,Ter97,Chi01])forbackgroundonR-trees.
Inparticular,[Chi01]showsthatanumberofotherdenitionsareequivalenttotheoneabove.
AparticularlyusefulfactisthatametricspacepX,dqisanR-treeifandonlyifitiscomplete,path-connected,andsatisestheso-calledfourpointcondition,thatis,(2.
1)dpx1,x2qdpx3,x4q¤maxtdpx1,x3qdpx2,x4q,dpx1,x4qdpx2,x3quforallx1,x4X.
LetTdenotethesetofisometryclassesofcompactR-trees.
InordertoequipTwithametric,recallthattheHausdordistancebetweentwoclosedsubsetsA,BofametricspacepX,dqisdenedas(2.
2)dHpA,Bq:inftε0:AUεpBqandBUεpAqu,whereUpCq:txX:dpx,Cq¤εu.
Basedonthisnotionofdistancebetweenclosedsets,wedenetheGromov-Hausdordistance,dGHpX,Yq,betweentwometricspacespX,dXqandpY,dYqastheinmumoftheHaus-dordistancedHpXI,YIqoverallmetricspacesXIandYIthatareisomor-phictoXandY,respectively,andthataresubspacesofsomecommonmetricspaceZ(compare[Gro99,BH99,BBI01]).
Adirectapplicationofthepreviousdenitionrequiresanoptimalem-beddingintoaspaceZwhichitisnotpossibletoobtainexplicitlyinmostexamples.
Wethereforegiveanequivalentreformulationwhichallowsustogetestimatesonthedistancebylookingfor"matchings"betweenthetwospacesthatpreservethetwometricsuptoanadditiveerror.
Inordertobemoreexplicit,werequiresomemorenotation.
AsubsetXYissaid6STEVENN.
EVANSANDANITAWINTERtobeacorrespondencebetweensetsXandYifforeachxXthereexistsatleastoneyYsuchthatpx,yq,andforeachyYthereexistsatleastonexXsuchthatpx,yq.
Thedistortionofisdenedby(2.
3)dispq:supt|dXpx1,x2qdYpy1,y2q|:px1,y1q,px2,y2qu.
Then(2.
4)dGHppX,dXq,pY,dYqq12infdispq,wheretheinmumistakenoverallcorrespondencesbetweenXandY(see,forexample,Theorem7.
3.
25in[BBI01]).
ItisshowninTheorem1in[EPW04]thatthemetricspacepT,dGHqiscompleteandseparable.
InthefollowingwewillbeinterestedincompactR-treespT,dqTequippedwithaprobabilitymeasureνontheBorelσ-eldBpTq.
WecallsuchobjectsweightedcompactR-treesandwriteTwtforthespaceofweight-preservingisometryclassesofweightedcompactR-trees,wherewesaythattwoweighted,compactR-treespX,d,νqandpXI,dI,νIqareweight-preservingisometricifthereexistsanisometryφbetweenXandXIsuchthatthepush-forwardofνbyφisνI:(2.
5)νIφν:νφ1.
Itisclearthatthepropertyofbeingweight-preservingisometricisanequiv-alencerelation.
WewanttoequipTwtwithaGromov-Hausdortypeofdistancewhichincorporatestheweightsonthetrees,butrstweneedtointroducesomenotionsthatwillbeusedinthedenition.
Anε-(distorted)isometrybetweentwometricspacespX,dXqandpY,dYqisa(possiblynon-measurable)mapf:XYsuchthat(2.
6)dispfq:supt|dXpx1,x2qdYpfpx1q,fpx2qq|:x1,x2Xu¤εandfpXqisanε-netinY.
ItiseasytoseethatiffortwometricspacespX,dXqandpY,dYqandε0wehavedGHpX,dXq,pY,dYq¨ε,thenthereexistsan2ε-isometryfromXtoY(compareLemma7.
3.
28in[BBI01]).
ThefollowingLemmastatesthatwemaychoosethedistortedisometrybetweenXandYtobemeasurableifweallowaslightlybiggerdistortion.
Lemma2.
1.
LetpX,dXqandpY,dYqbetwocompactrealtreessuchthatdGHpX,dXq,pY,dYq¨εforsomeε0.
Thenthereexistsameasurable3ε-isometryfromXtoY.
Proof.
IfdGHpX,dXq,pY,dYq¨ε,thenby(2.
4)thereexistsacorrespon-dencebetweenXandYsuchthatdispq2ε.
SincepX,dXqiscom-pactthereexistsaniteε-netinX.
Weclaimthatforeachsuchniteε-netSX,εtx1,.
.
.
,xNεuX,anysetSY,εty1,.
.
.
,yNεuYsuchthatSUBTREEPRUNEANDRE-GRAFT7pxi,yiqforallit1,2,.
.
.
,Nεuisan3ε-netinY.
Toseethis,xyY.
Wehavetoshowtheexistenceofit1,2,.
.
.
,NεuwithdYpyi,yq3ε.
ForthatchoosexXsuchthatpx,yq.
SinceSX,εisanε-netinXthereex-istsanit1,2,.
.
.
,NεusuchthatdXpxi,xqε.
pxi,yiqimpliesthereforethat|dXpxi,xqdYpyi,yq|¤dispq2ε,andhencedYpyi,yq3ε.
FurthermorewemaydecomposeXintoNεpossiblyemptymeasurabledisjointsubsetsofXbylettingX1,ε:Bpx1,εq,X2,ε:Bpx2,εqzX1,ε,andsoon,whereBpx,rqistheopenballtxIX:dXpx,xIqru.
ThenfdenedbyfpxqyiforxXi,εisobviouslyameasurable3ε-isometryfromXtoY.
WealsoneedtorecallthedenitionoftheProhorovdistancebetweentwoprobabilitymeasures(see,forexample,[EK86]).
GiventwoprobabilitymeasuresandνonametricspacepX,dqwiththecorrespondingcollectionofclosedsetsdenotedbyC,theProhorovdistancebetweenthemisdPp,νq:inftε0:pCq¤νpCεqεforallCCu,whereCε:txX:infyCdpx,yqεu.
TheProhorovdistanceisametriconthecollectionofprobabilitymeasuresonX.
Thefollowingresultshowsthatifwepushmeasuresforwardwithamaphavingasmalldistortion,thenProhorovdistancescan'tincreasetoomuch.
Lemma2.
2.
SupposethatpX,dXqandpY,dYqaretwometricspaces,f:XYisameasurablemapwithdispfq¤ε,andandνaretwoprobabilitymeasuresonX.
ThendPpf,fνq¤dPp,νqε.
Proof.
SupposethatdPp,νqδ.
Bydenition,pCq¤νpCδqδforallclosedsetsCC.
IfDisaclosedsubsetofY,thenfpDqpf1pDqq¤pf1pDqq¤νpf1pDqδqδνpf1pDqδqδ.
(2.
7)NowxIf1pDqδmeansthereisxPXsuchthatdXpxI,xPqδandfpxPqD.
Bytheassumptionthatdispfq¤ε,wehavedYpfpxIq,fpxPqqδε,andhencefpxIqDδε.
Thus(2.
8)f1pDqδf1pDδεqandwehave(2.
9)fpDq¤νpf1pDδεqqδfνpDδεqδ,sothatdPpf,fνq¤δε,asrequired.
8STEVENN.
EVANSANDANITAWINTERWearenowinapositiontodenetheweightedGromov-Hausdordis-tancebetweenthetwocompact,weightedR-treespX,dX,νXqandpY,dY,νYq.
Forε0,set(2.
10)FεX,Y:2measurableε-isometriesfromXtoY@.
Put(2.
11)GHwtpX,Yq:inf5ε0:existfFεX,Y,gFεY,XsuchthatdPpfνX,νYq¤ε,dPpνX,gνYq¤εC.
Notethatthesetontherighthandsideisnon-emptybecauseXandYarecompact,andhencebounded.
ItwillturnoutthatGHwtsatisesallthepropertiesofametricexceptthetriangleinequality.
Torectifythis,let(2.
12)dGHwtpX,Yq:inf5n1i1GHwtpZi,Zi1q14C,wheretheinmumistakenoverallnitesequencesofcompact,weightedR-treesZ1,.
.
.
ZnwithZ1XandZnY.
Lemma2.
3.
ThemapdGHwt:TwtTwtRisametriconTwt.
Moreover,12GHwtpX,Yq14¤dGHwtpX,Yq¤GHwtpX,Yq14forallX,YTwt.
Proof.
Itisimmediatefrom(2.
11)thatthemapGHwtissymmetric.
Wenextclaimthat(2.
13)GHwtpX,dX,νXq,pY,dY,νYq¨0,ifandonlyifpX,dX,νXqandpY,dY,νYqareweight-preservingisometric.
The"if"directionisimmediate.
Noterstfortheconversethat(2.
13)impliesthatforallε0thereexistsanε-isometryfromXtoY,andtherefore,byLemma7.
3.
28in[BBI01],dGHpX,dXq,pY,dYq¨2ε.
ThusdGHpX,dXq,pY,dYq¨0,anditfollowsfromTheorem7.
3.
30of[BBI01]thatpX,dXqandpY,dYqareisometric.
Checkingtheproofofthatresult,weseethatwecanconstructanisometryf:XYbytakinganydensecountablesetSX,anysequenceoffunctionspfnqsuchthatfnisanεn-isometrywithεn0asnV,andlettingfbelimkfnkalonganysubsequencesuchthatthelimitexistsforallxS(suchasubsequenceexistsbythecompactnessofY).
Therefore,xsomedensesubsetSXandsupposewithoutlossofgeneralitythatwehaveanisometryf:XYgivenbyfpxqlimnVfnpxq,xS,wherefnFεnX,Y,dPpfnνX,νYq¤εn,SUBTREEPRUNEANDRE-GRAFT9andlimnVεn0.
WewillbedoneifwecanshowthatfνXνY.
IfXisadiscretemeasurewithatomsbelongingtoS,thendPpfνX,νYq¤limsupndPpfnνX,νYqdPpfnX,fnνXqdPpfX,fnXqdPpfνX,fXq%¤2dPpX,νXq,(2.
14)wherewehaveusedLemma2.
2andthefactthatlimnVdPpfX,fnXq0becauseofthepointwiseconvergenceoffntofonS.
BecausewecanchooseXsothatdPpX,νXqisarbitrarilysmall,weseethatfνXνY,asrequired.
NowconsiderthreespacespX,dX,νXq,pY,dY,νYq,andpZ,dZ,νZqinTwt,andconstantsε,δ0,suchthatGHwtpX,dX,νXq,pY,dY,νYq¨εandGHwtpY,dY,νYq,pZ,dZ,νZq¨δ.
ThenthereexistfFεX,YandgFδY,ZsuchthatdPpfνX,νYqεanddPpgνY,νZqδ.
NotethatgfFεδX,Z.
Moreover,byLemma2.
2(2.
15)dPppgfqνX,νZq¤dPpgνY,νZqdPpgfνX,gνYqδεδ.
This,andasimilarargumentwiththerolesofXandZinterchanged,showsthat(2.
16)GHwtpX,Zq¤2rGHwtpX,YqGHwtpY,Zqs.
Thesecondinequalityinthestatementofthelemmaisclear.
Inordertoseetherstinequality,itsucestoshowthatforanyZ1,.
.
.
Znwehave(2.
17)GHwtpZ1,Znq14¤2n1i1GHwtpZi,Zi1q14.
Wewillestablish(2.
17)byinduction.
Theinequalitycertainlyholdswhenn2.
Supposeitholdsfor2,n1.
WriteSforthevalueofthesumontherighthandsideof(2.
17).
Put(2.
18)k:max51¤m¤n1:m1i1GHwtpZi,Zi1q14¤S{2C.
Bytheinductivehypothesisandthedenitionofk,(2.
19)GHwtpZ1,Zkq14¤2k1i1GHwtpZi,Zi1q14¤2pS{2qS.
Ofcourse,(2.
20)GHwtpZk,Zk1q14¤SBydenitionofk,(2.
21)ki1GHwtpZi,Zi1q14S{2,10STEVENN.
EVANSANDANITAWINTERsothatoncemorebytheinductivehypothesis,(2.
22)GHwtpZk1,Znq14¤2n1ik1GHwtpZi,Zi1q142S2ki1GHwtpZi,Zi1q14¤S.
From(2.
19),(2.
20),(2.
22)andtwoapplicationsof(2.
16)wehaveGHwtpZ1,Znq14¤t4rGHwtpZ1,ZkqGHwtpZk,Zk1qGHwtpZk1,Znqsu14¤p43S4q14¤2S,(2.
23)asrequired.
ItisobviousbyconstructionthatdGHwtsatisesthetriangleinequality.
TheotherpropertiesofametricfollowfromthecorrespondingpropertieswehavealreadyestablishedforGHwtandtheboundsinthestatementofthelemmawhichwehavealreadyestablished.
TheprocedureweusedtoconstructtheweightedGromov-Hausdormet-ricdGHwtfromthesemi-metricGHwtwasadaptedfromaproofin[Kel75]ofthecelebratedresultofAlexandroandUrysohnonthemetrizabilityofuniformspaces.
Thatproofwas,inturn,adaptedfromearlierworkofFrinkandBourbaki.
Thechoiceofthepower14isnotparticularlyspecial,anysucientlysmallpowerwouldhaveworked.
Theorem2.
5belowsaysthatthemetricspacepTwt,dGHwtqiscompleteandseparableandhenceisareasonablespaceonwhichtodoprobabilitytheory.
Inordertoprovethisresult,weneedacompactnesscriterionthatwillbeusefulinitsownright.
Proposition2.
4.
AsubsetDofpTwt,dGHwtqisrelativelycompactifandonlyifthesubsetE:tpT,dq:pT,d,νqDuinpT,dGHqisrelativelycompact.
Proof.
The"onlyif"directionisclear.
AssumefortheconversethatEisrelativelycompact.
SupposethatppTn,dTn,νTnqqnNisasequenceinD.
Byassumption,ppTn,dTnqqnNhasasubsequenceconvergingtosomepointpT,dTqofpT,dGHq.
Foreaseofnotation,wewillrenumberandalsodenotethissubsequencebyppTn,dTnqqnN.
Forbrevity,wewillalsoomitspecicmentionofthemetriconarealtreewhenitisclearfromthecontext.
ByProposition7.
4.
12in[BBI01],foreachε0thereisaniteε-netTεinTandforeachnNaniteε-netTεn:txε,1n,.
.
.
,xε,#TεnnuinTnsuchthatdGHpTεn,Tεq0asnV.
Moreover,wetake#Tεn#TεNε,say,forSUBTREEPRUNEANDRE-GRAFT11nsucientlylarge,andso,bypassingtoafurthersubsequenceifnecessary,wemayassumethat#Tεn#TεNεforallnN.
WemaythenassumethatTεnandTεhavebeenindexedsothatthatlimnVdTnpxε,in,xε,jnqdTpxε,i,xε,jqfor1¤i,j¤Nε.
WemaybeginwiththeballsofradiusεaroundeachpointofTεnandde-composeTnintoNεpossiblyempty,disjoint,measurablesetstTε,1n,.
.
.
,Tε,Nεnuofradiusnogreaterthanε.
Deneameasurablemapfεn:TnTεnbyfεnpxqxε,inifxTε,inandletgεnbetheinclusionmapfromTεntoTn.
Byconstruction,fεnandgεnaremeasurableε-isometries.
Moreover,dPpgεnqpfεnqνn,νn¨εand,ofcourse,dPpfεnqνn,pfεnqνn¨0.
Thus,GHwtppTεn,pfεnqνnq,pTn,νnqq¤ε.
Bysimilarreasoning,ifwedenehεn:TεnTεbyxε,inxε,i,thenlimnVGHwtppTεn,pfεnqνnq,pTε,phεnqνnqq0.
SinceTεisnite,bypassingtoasubsequence(andrelabelingasbefore)wehavelimnVdPpphεnqνn,νεq0forsomeprobabilitymeasureνεonTε,andhencelimnVGHwtppTε,phεnqνnq,pTε,νεqq0.
Therefore,byLemma2.
3,limsupnVdGHwtppTn,νnq,pTε,phεnqνnqq¤ε14.
Now,sincepT,dTqiscompact,thefamilyofmeasurestνε:ε0uisrelativelycompact,andsothereisaprobabilitymeasureνonTsuchthatνεconvergestoνintheProhorovdistancealongasubsequenceε0andhence,byargumentssimilartotheabove,alongthesamesubsequenceGHwtppTε,νεq,pT,νqqconvergesto0.
AgainapplyingLemma2.
3,wehavethatdGHwtppTε,νεq,pT,νqqconvergesto0alongthissubsequence.
Combiningtheforegoing,weseethatbypassingtoasuitablesubsequenceandrelabeling,dGHwtppTn,νnq,pT,νqqconvergesto0,asrequired.
Theorem2.
5.
ThemetricspacepTwt,dGHwtqiscompleteandseparable.
Proof.
SeparabilityfollowsreadilyfromseparabilityofpT,dGHq(seeThe-orem1in[EPW04]),andtheseparabilitywithrespecttotheProhorovdistanceoftheprobabilitymeasuresonaxedcomplete,separablemetricspace(see,forexample,[EK86]),andLemma2.
3.
Itremainstoestablishcompleteness.
Byastandardargument,itsucestoshowthatanyCauchysequenceinTwthasaconvergentsubsequence.
LetpTn,dTn,νnqnNbeaCauchysequenceinTwt.
ThenpTn,dTnqnNisaCauchysequenceinTbyLemma2.
3.
ByTheorem1in[EPW04]thereisaTTsuchthatdGHpTn,Tq0,asnV.
Inparticular,thesequence12STEVENN.
EVANSANDANITAWINTERpTn,dTnqnNisrelativelycompactinT,andtherefore,byProposition2.
4,pTn,dTn,νnqnNisrelativelycompactinTwt.
ThuspTn,dTn,νnqnNhasaconvergentsubsequence,asrequired.
WeconcludethissectionbygivinganecessaryandsucientconditionforasubsetofpT,dGHqtoberelativelycompact,andhence,byProposi-tion2.
4,anecessaryandsucientconditionforasubsetofpTwt,dGHwtqtoberelativelycompact.
FixpT,dqT,and,asusual,denotetheBorel-σ-algebraonTbyBpTq.
Let(2.
24)To¤a,bTsa,brtheskeletonofT.
ObservethatifTITisadensecountableset,then(2.
24)holdswithTreplacedbyTI.
Inparticular,ToBpTqandBpTq§§Toσptsa,br;a,bTIuq,whereBpTq§§To:tATo;ABpTqu.
Hencethereexistsauniqueσ-nitemeasureTonT,calledlengthmeasure,suchthatTpTzToq0and(2.
25)Tpsa,brqdpa,bq,da,bT.
SuchameasuremaybeconstructedasthetraceontoToofone-dimensionalHausdormeasureonT,andastandardmonotoneclassargumentshowsthatthisistheuniquemeasurewithproperty(2.
25).
Forε0,TT,andρTwrite(2.
26)RεpT,ρq:txT:hyT,rρ,ysx,dTpx,yqεutρu.
fortheε-trimmingrelativetotherootρofthecompactR-treeT.
Thenset(2.
27)RεpTq:4ρTRεpT,ρq,diampTqε,singleton,diampTq¤ε,wherebysingletonwemeanthetrivialR-treeconsistingofonepoint.
ThetreeRεpTqiscalledtheε-trimmingofthecompactR-treeT.
Lemma2.
6.
AsubsetEofpT,dGHqisrelativelycompactifandonlyifforallε0,(2.
28)suptTpRεpTqq:TEuV.
Proof.
The"onlyif"directionfollowsfromthefactthatTTpRεpTqqiscontinuous,whichisessentiallyLemma7.
3of[EPW04].
Conversely,supposethat(2.
28)holds.
GivenTE,anε-netforRεpTqisa2ε-netforT.
ByLemma2.
7below,RεpTqhasanε-netofcardinal-ityatmostpε2q1TpRεpTqq$pε2q1TpRεpTqq1$.
Byassumption,thelastquantityisuniformlyboundedinTE.
ThusEisuniformlytotallyboundedandhenceisrelativelycompactbyTheorem7.
4.
15of[BBI01].
Lemma2.
7.
LetTTbesuchthatTpTqV.
Foreachε0thereisanε-netforTofcardinalityatmostpε2q1TpTq$pε2q1TpTq1$SUBTREEPRUNEANDRE-GRAFT13Proof.
Notethatanε2-netforRε2pTqwillbeanε-netforT.
ThesetTzRε2pTqisacollectionofdisjointsubtrees,oneforeachleafofRε2pTq,andeachsuchsubtreeisofdiameteratleastε2.
ThusthenumberofleavesofRε2pTqisatmostpε2q1TpTq.
EnumeratetheleavesofRε2pTqasx0,x1,xn.
Eacharcrx0,xis,1¤i¤n,ofRε2pTqhasanε2-netofcardinalityatmostpε2q1dTpx0,xiq1¤pε2q1TpTq1.
Therefore,bytakingtheunionofthesenets,Rε2pTqhasanε2-netofcardinalityatmostpε2q1TpTq$pε2q1TpTq1$.
Remark2.
8.
TheboundinLemma2.
7isfarfromoptimal.
ItcanbeshownthatThasanε-netwithacardinalitythatisoforderTpTq{ε.
Thisisclearfornitetrees(thatis,treeswithanitenumberofbranchpoints),wherewecantraversethetreewithaunitspeedpathandhencethinkofthetreeasanimageoftheintervalr0,2TpTqsbyaLipschitzmapwithLipschitzconstant1,sothatacoveringoftheintervalr0,2TpTqsbyε-ballsgivesacoveringofTbyε-balls.
ThisargumentcanbeextendedtoarbitrarynitelengthR-trees,butthedetailsaretediousandsowehavecontentedourselveswiththeabovesimplerbound.
3.
TreesandcontinuouspathsForthesakeofcompletenessandtoestablishsomenotationwerecallsomefactsabouttheconnectionbetweencontinuousexcursionpathsandtrees(see[Ald93,LG99,DLG02]formoreonthisconnection).
WriteCpRqforthespaceofcontinuousfunctionsfromRintoR.
ForeCpRq,putζpeq:inftt0:eptq0uandwrite(3.
1)U:687eCpRq:ep0q0,ζpeqV,eptq0for0tζpeq,andeptq0fortζpeqDFEforthespaceofpositiveexcursionpaths.
SetU:teU:ζpequ.
WeassociateeacheU1withacompactR-treeasfollows.
Deneanequivalencerelationeonr0,1sbyletting(3.
2)u1eu2,iepu1qinfuru1u2,u1u2sepuqepu2q.
Considerthefollowingpseudo-metriconr0,1s(3.
3)dTepu1,u2q:epu1q2infuru1u2,u1u2sepuqepu2q,whichbecomesatruemetriconthequotientspaceTe:R§§er0,1s§§e.
Lemma3.
1.
ForeacheU1themetricspacepTe,dTeqisacompactR-tree.
14STEVENN.
EVANSANDANITAWINTERProof.
Itisstraightforwardtocheckthatthequotientmapfromr0,1sontoTeiscontinuouswithrespecttodTe.
ThuspTe,dTeqispath-connectedandcompactasthecontinuousimageofametricspacewiththeseproperties.
Inparticular,pTe,dTeqiscomplete.
Tocompletetheproof,itthereforesucestoverifythefourpointcondi-tion(2.
1).
However,foru1,u2,u3,u4Tewehave(3.
4)maxtdTepu1,u3qdTepu2,u4q,dTepu1,u4qdTepu2,u3qudTepu1,u2qdTepu3,u4q,wherestrictinequalityholdsifandonlyif(3.
5)minijinfuruiuj,uiujsepuq4infuru1u2,u1u2sepuq,infuru3u4,u3u4sepuqB.
Remark3.
2.
AnycompactR-treeTisisometrictoTeforsomeeU1.
Toseethis,xarootρT.
RecallRεpT,ρq,theε-trimmingofTwithrespecttoρdenedin(2.
26).
LetbeaprobabilitymeasureonTthatisequiv-alenttothelengthmeasureT.
BecauseTisσ-nite,suchaprobabilitymeasurealwaysexists,butonecanconstructexplicitlyasfollows:setH:maxuTdpρ,uq,andput:21TpRpρ,21Hq¤qTpRpρ,21Hqqi22iTpRpρ,2iHqzRpρ,2i1Hq¤qTpRpρ,2iHqzRpρ,2i1Hqq.
Forall0εHthereisacontinuouspathfε:r0,2TpRεpT,ρqqsRεpT,ρqsuchthathεdenedbyhεptq:dpρ,fεptqqbelongstoU2TpRεpT,ρqq(inpar-ticular,fεp0qfεp2TpRεpT,ρqqqρ),hεispiecewiselinearwithslopes¨1,andThεisisometrictoRεpT,ρq.
Moreover,thesepathsmaybechosenconsistentlysothatifεI¤εP,thenfεPptqfεIpinfts0:|t0¤r¤s:fεIprqRεPpT,ρqu|tuq,where|¤|denotesLebesguemeasure.
NowdeneeεUpRεpT,ρqqtobetheabsolutelycontinuouspathsatisfyingdeεptqdt2dTdpfεptqqdhεptqdt.
ItcanbeshownthateεconvergesuniformlytosomeeU1asε0andthatTeisisometrictoT.
SUBTREEPRUNEANDRE-GRAFT15Fromtheconnectionwehaverecalledbetweenexcursionpathsandrealtrees,itshouldbeclearthattheanalogueofanSPRmoveforarealtreearisingfromanexcursionpathistheexcisionandre-insertionofasub-excursion.
Figure2illustratessuchanoperation.
Figure2.
Asubtreepruneandre-graftoperationonanexcursionpath:theexcursionstartingattimeuinthetoppictureisexcisedandinsertedattimev,andtheresultinggapbetweenthetwopointsmarked#isclosedup.
Thetwopointsmarked#(resp.
)inthetop(resp.
bottom)picturecorrespondtoasinglepointintheassociatedR-tree.
EachtreecomingfromapathinU1hasanaturalweightonit:foreU1,weequippTe,dTeqwiththeweightνTegivenbythepush-forwardofLebesguemeasureonr0,1sbythequotientmap.
Wenishthissectionwitharemarkaboutthenaturallengthmeasureonatreecomingfromapath.
GiveneU1anda0,let(3.
6)Ga:687tr0,1s:eptqaand,forsomeε0,epuqaforallust,tεr,eptεqa.
DFEdenotethecountablesetofstartingpointsofexcursionsofthefunctioneabovethelevela.
ThenTe,thelengthmeasureonTe,isjustthepush-forwardofthemeasureV0da°tGaδtbythequotientmap.
Alternatively,16STEVENN.
EVANSANDANITAWINTERwrite(3.
7)Γe:tps,aq:ss0,1r,ar0,epsqrufortheregionbetweenthetimeaxisandthegraphofe,andforps,aqΓedenotebyspe,s,aq:suptrs:eprqauandspe,s,aq:inftts:eptqauthestartandnishoftheexcursionofeabovelevelathatstraddlestimes.
ThenTeisthepush-forwardofthemeasureΓedsda1spe,s,aqspe,s,aqδspe,s,aqbythequotientmap.
WenotethatthemeasureTeappearsin[AS02].
4.
UniformrandomweightedcompactR-trees:thecontinuumrandomtreeInthissectionwewillrecallthedenitionofAldous'scontinuumran-domtree,whichcanbethoughtofasauniformlychosenrandomweightedcompactR-tree.
ConsidertheItoexcursionmeasureforexcursionsofstandardBrownianmotionawayfrom0.
Thisσ-nitemeasureisdenedsubjecttoanormal-izationofBrownianlocaltimeat0,andwetaketheusualnormalizationoflocaltimesateachlevelwhichmakesthelocaltimeprocessanoccupationdensityinthespatialvariableforeachxedvalueofthetimevariable.
Theexcursionmeasureisthesumoftwomeasures,onewhichisconcentratedonnon-negativeexcursionsandonewhichisconcentratedonnon-positiveexcursions.
LetNbethepartwhichisconcentratedonnon-negativeex-cursions.
Thus,inthenotationofSection3,Nisaσ-nitemeasureonU,whereweequipUwiththeσ-eldUgeneratedbythecoordinatemaps.
Deneamapv:UU1byeepζpeq¤qζpeq.
Then(4.
1)PpΓq:Ntv1pΓqteU:ζpeqcuuNteU:ζpeqcu,ΓU,doesnotdependonc0(see,forexample,Exercise12.
2.
13.
2in[RY99]).
TheprobabilitymeasurePiscalledthelawofnormalizednon-negativeBrownianexcursion.
Wehave(4.
2)NteU:ζpeqdcudc22πc3and,deningSc:U1Ucby(4.
3)Sce:cep¤{cqwehave(4.
4)NpdeqGpeqV0dc22πc3U1PpdeqGpSceqforanon-negativemeasurablefunctionG:UR.
RecallfromSection3howeacheU1isassociatedwithaweightedcom-pactR-treepTe,dTe,νTeq.
LetPbetheprobabilitymeasureonpTwt,dGHwtqSUBTREEPRUNEANDRE-GRAFT17thatisthepush-forwardofthenormalizedexcursionmeasurebythemapepT2e,dT2e,νT2eq,where2eU1isjusttheexcursionpatht2eptq.
TheprobabilitymeasurePisthedistributionofanobjectconsistingofAldous'scontinuumrandomtreealongwithanaturalmeasureonthistree(see,forexample,[Ald91a,Ald93]).
ThecontinuumrandomtreearisesasthelimitofauniformrandomtreeonnverticeswhennVandedgelengthsarerescaledbyafactorof1{n.
Theappearanceof2eratherthaneinthedenitionofPisaconsequenceofthischoiceofscaling.
Theassociatedprobabilitymeasureoneachrealizationofthecontinuumrandomtreeisthemeasurethatarisesinthislimitingconstructionbytakingtheuniformprobabilitymeasureonrealizationsoftheapproximatingnitetrees.
TheprobabilitymeasurePcanthereforebeviewedinformallyasthe"uniformdistribution"onpTwt,dGHwtq.
5.
CampbellmeasurefactsForthepurposesofconstructingtheMarkovprocessthatisofinteresttous,weneedtounderstandpickingarandomweightedtreepT,dT,νTqaccordingtothecontinuumrandomtreedistributionP,pickingapointuaccordingtothelengthmeasureTandanotherpointvaccordingtotheweightνT,andthendecomposingTintotwosubtreesrootedatu–onethatcontainsvandonethatdoesnot(wearebeingalittleimprecisehere,becauseTwillbeaninnitemeasure,Palmostsurely).
Inordertounderstandthisdecomposition,wemustunderstandthecor-respondingdecompositionofexcursionpathsundernormalizedexcursionmeasure.
Becausesubtreescorrespondtosub-excursionsandbecauseofourobservationinSection3thatforanexcursionethelengthmeasureTeonthecorrespondingtreeisthepush-forwardofthemeasureΓedsda1spe,s,aqspe,s,aqδspe,s,aqbythequotientmap,weneedtounderstandthedecompositionoftheexcursioneintotheexcursionaboveathatstraddlessandthe"remaining"excursionwhenwheneischosenaccordingtothestandardBrownianexcursiondistributionPandps,aqischosenaccordingtotheσ-nitemeasuredsda1spe,s,aqspe,s,aqonΓe–seeFigure3.
GivenanexcursioneUandalevela0write:ζpeq:inftt0:eptq0uforthe"length"ofe,atpeqforthelocaltimeofeatlevelauptotimet,eaforetime-changedbytheinverseoftt0ds1tepsq¤au(thatis,eaisewiththesub-excursionsabovelevelaexcisedandthegapsclosedup),atpeaqforthelocaltimeofeaatthelevelauptotimet,Uapeqforthesetofsub-excursionintervalsofeabovea(thatis,anelementofUapeqisanintervalIrgI,dIssuchthatepgIqepdIqaandeptqaforgItdI),NapeqforthecountingmeasurethatputsaunitmassateachpointpsI,eIq,where,forsomeIUapeq,sI:agIpeqistheamountof18STEVENN.
EVANSANDANITAWINTERFigure3.
Thedecompositionoftheexcursione(toppic-ture)intotheexcursiones,aabovelevelathatstraddlestimes(bottomleftpicture)andthe"remaining"excursionˇes,a(bottomrightpicture).
localtimeofeatlevelaaccumulateduptothebeginningofthesub-excursionIandeIUisgivenby(5.
1)eIptqepgItqa,0¤t¤dIgI,0,tdIgI,isthecorrespondingpieceofthepatheshiftedtobecomeanexcur-sionabovethelevel0startingattime0,es,aUandˇes,aU,forthesubexcursion"above"ps,aqΓe,thatis,(5.
2)es,aptq:4epspe,s,aqtqa,0¤t¤spe,s,aqspe,s,aq,0,tspe,s,aqspe,s,aq,respectively"below"ps,aqΓe,thatis,(5.
3)ˇes,aptq:4eptq,0¤t¤spe,s,aq,eptspe,s,aqspe,s,aqq,tspe,s,aq.
σaspeq:inftt0:atpeqsuandτaspeq:inftt0:atpeqsu,SUBTREEPRUNEANDRE-GRAFT19es,aUforewiththeintervalsσaspeq,τaspeqrcontaininganexcursionabovelevelaexcised,thatis,(5.
4)es,aptq:eptq,0¤t¤σaspeq,eptτaspeqσaspeqq,tσaspeq.
Thefollowingpathdecompositionresultundertheσ-nitemeasureNispreparatorytoadecompositionundertheprobabilitymeasureP,Corollary5.
2,thathasasimplerintuitiveinterpretation.
Proposition5.
1.
Fornon-negativemeasurablefunctionsFonRandG,HonU,NpdeqΓedsdaspe,s,aqspe,s,aqFpspe,s,aqqGpes,aqHpˇes,aqNpdeqV0daNapeqpdpsI,eIqqFpσasIpeqqGpeIqHpesI,aqNrGsNHζ0dsFpsq$.
Proof.
TherstequalityisjustachangeintheorderofintegrationandhasalreadybeenremarkeduponinSection3.
Standardexcursiontheory(see,forexample,[RW00,RY99,Ber96])saysthatunderN,therandommeasureeNapeqconditionaloneeaisaPoissonrandommeasurewithintensitymeasureλapeqN,whereλapeqisLebesguemeasurerestrictedtotheintervalr0,aVpeqsr0,2aVpeaqs.
NotethatesI,aisconstructedfromeaandNapeqδpsI,eIqinthesamewaythateisconstructedfromeaandNapeq.
Also,σasIpesI,aqσasIpeq.
Therefore,bytheCampbell-PalmformulaforPoissonrandommeasures(see,forexample,Section12.
1of[DVJ88]),NpdeqV0daNapeqpdpsI,eIqqFpσasIpeqqGpeIqHpesI,aqNpdeqV0daNNapeqpdpsI,eIqqFpσasIpeqqGpeIqHpesI,aq§§§ea%NpdeqV0daNrGsN3aVpeq0dsIFpσasIpeqqAH§§§ea%NrGsV0daNpdeq3daspeqFpsqAHpeqNrGsNpdeq3V0dadaspeqFpsqAHpeqNrGsNHζ0dsFpsq%.
20STEVENN.
EVANSANDANITAWINTERThenextresultsaysthatifwepickanexcursioneaccordingtothestandardexcursiondistributionPandthenpickapointps,aqΓeaccordingtotheσ-nitelengthmeasurecorrespondingtothelengthmeasureTeontheassociatedtreeTe(seetheendofSection3),thenthefollowingobjectsareindependent:(a)thelengthoftheexcursionabovelevelathatstraddlestimes,(b)theexcursionobtainedbytakingtheexcursionabovelevelathatstraddlestimes,turningit(byashiftofaxes)intoanexcursiones,aabovelevelzerostartingattimezero,andthenBrownianre-scalinges,atoproduceanexcursionofunitlength,(c)theexcursionobtainedbytakingtheexcursionˇes,athatcomesfromexcisinges,aandclosingupthegap,andthenBrownianre-scalingˇes,atoproduceanexcursionofunitlength,(d)thestartingtimespe,s,aqoftheexcursionabovelevelathatstrad-dlestimesrescaledbythelengthofˇes,atogiveatimeintheintervalr0,1s.
Moreover,thelengthin(a)is"distributed"accordingtotheσ-nitemea-sure(5.
5)122πdρp1ρqρ3,0¤ρ¤1,theunitlengthexcursionsin(b)and(c)arebothdistributedasstandardBrownianexcursions(thatis,accordingtoP),andthetimein(d)isuni-formlydistributedontheintervalr0,1s.
Recallfrom(4.
3)thatSc:U1UcistheBrownianre-scalingmapdenedbySce:cep¤{cq.
Corollary5.
2.
Fornon-negativemeasurablefunctionsFonRandKonUU,PpdeqΓedsdaspe,s,aqspe,s,aqFspe,s,aqζpˇes,aqKpes,a,ˇes,aq310duFpuqAPpdeqΓedsdaspe,s,aqspe,s,aqKpes,a,ˇes,aq310duFpuqA122π10dρp1ρqρ3PpdeIqPpdePqKpSρeI,S1ρePq.
SUBTREEPRUNEANDRE-GRAFT21Proof.
Foranon-negativemeasurablefunctionLonUU,itfollowsstraight-forwardlyfromProposition5.
1that(5.
6)NpdeqΓedsdaspe,s,aqspe,s,aqFspe,s,aqζpˇes,aqLpes,a,ˇes,aq310duFpuqANpdeIqNpdePqLpeI,ePqζpePq.
Theleft-handsideofequation(5.
6)is,by(4.
4),(5.
7)V0dc22πc3PpdeqΓScedsdaFspSce,s,aqζp}Sces,aqLpySces,a,}Sces,aqspSce,s,aqspSce,s,aq.
Ifwechangevariablestots{candba{c,thentheintegralforps,aqoverΓScebecomesanintegralforpt,bqoverΓe.
Also,(5.
8)spSce,ct,cbqsup3rct:cerccbAcsuptrt:eprqbucspe,t,bq,and,bysimilarreasoning,(5.
9)spSce,ct,cbqcspe,t,bqand(5.
10)ζp}Scect,`cbqcζpˇet,bq.
Thus(5.
7)is(5.
11)V0dc22πc3PpdeqcΓedtdbFspe,t,bqζpˇet,bq¨LpyScect,`cb,}Scect,`cbqspe,t,bqspe,t,bq.
NowsupposethatLisoftheform(5.
12)LpeI,ePqKpRζpeIqζpePqeI,RζpeIqζpePqePqMpζpeIqζpePqqζpeIqζpePq,where,foreaseofnotation,weputforeU,andc0,(5.
13)Rce:Sc1e1cepc¤q.
Then(5.
11)becomes(5.
14)V0dc22πc3PpdeqΓedtdbFspe,t,bqζpˇet,bqKpet,b,ˇet,bqMpcqspe,t,bqspe,t,bq.
22STEVENN.
EVANSANDANITAWINTERSince(5.
14)wasshowntobeequivalenttothelefthandsideof(5.
6),itfollowsfrom(4.
4)that(5.
15)PpdeqΓedtdbspe,t,bqspe,t,bqFspe,t,bqζpˇet,bq¨Kpet,b,ˇet,bq10duFpuqNrMsNpdeIqNpdePqLpeI,ePqζpePq,andtherstequalityofthestatementfollows.
Wehavefromtheidentity(5.
15)that,foranyC0,NtζpeqCuPpdeqΓedsdaspe,s,aqspe,s,aqKpes,a,ˇes,aqNpdeIqNpdePqKpRζpeIqζpePqeI,RζpeIqζpePqePq1tζpeIqζpePqCuζpeIqζpePqζpePqV0dcI22πcI3V0dcP22πcPPpdeIqPpdePqKpRcIcPScIeI,RcIcPScPePq1tcIcPCucIcP.
MakethechangeofvariablesρcIcIcPandξcIcP(withcorrespond-ingJacobianfactorξ)togetV0dcI22πcI3V0dcP22πcPPpdeIqPpdePqKpRcIcPScIeI,RcIcPScPePq1tcIcPCucIcP122π2V0dξ10dρξρ3p1ρqξ41tξCuξPpdeIqPpdePqKpSρeI,S1ρePq122π25VCdξξ3C10dρρ3p1ρqPpdeIqPpdePqKpSρeI,S1ρePq,andthecorollaryfollowsuponrecalling(4.
2).
Corollary5.
3.
(i)Forx0,PpdeqΓedsdaspe,s,aqspe,s,aq1tmax0¤t¤ζpes,aqes,axu2Vn1nxexpp2n2x2qSUBTREEPRUNEANDRE-GRAFT23(ii)For0p¤1,PpdeqΓedsdaspe,s,aqspe,s,aq1tζpes,aqpu1p2πp.
Proof.
(i)RecallrstofallfromTheorem5.
2.
10in[Kni81]that(5.
16)P4eU1:max0¤t¤1eptqxB2Vn1p4n2x21qexpp2n2x2q.
ByCorollary5.
2appliedtoKpeI,ePq:1tmaxtr0,ζpeIqseIptqxuandF1,PpdeqΓedsdaspe,s,aqspe,s,aq1tmax0¤t¤ζpes,aqes,axu122π10dρρ3p1ρqP4maxtr0,ρsρept{ρqxB122π10dρρ3p1ρqP4maxtr0,1septqxρB122π10dρρ3p1ρq2Vn14n2x2ρ1exp2n2x2ρ2Vn1nxexpp2n2x2q,asclaimed.
(ii)Corollary5.
2appliedtoKpeI,ePq:1tζpeIqpuandF1immediatelyyieldsPpdeqΓedsdaspe,s,aqspe,s,aq1tζpes,aqpu122π1pdρρ3p1ρq1p2πp.
Weconcludethissectionbycalculatingtheexpectationsofsomefunc-tionalswithrespecttoP(the"uniformdistribution"onpTwt,dGHwtqasintroducedintheendofSection4).
ForTTwt,andρT,recallRcpT,ρqfrom(2.
26),andthelengthmeasureTfrom(2.
25).
GivenpT,dqTwtandu,vT,let(5.
17)ST,u,v:twT:usv,wru,denotethesubtreeofTthatdiersfromitsclosurebythepointu,whichcanbethoughtofasitsroot,andconsistsofpointsthatareonthe"otherside"ofufromv(recallsv,wristheopenarcinTbetweenvandw).
24STEVENN.
EVANSANDANITAWINTERLemma5.
4.
(i)Forx0,PTνT2pu,vqTT:heightpST,u,vqx@$PTνTpdvqTpRxpT,vqq%2Vn1nxexppn2x2{2q.
(ii)For1αV,PTνTpdvqTTpduqheightpST,u,vq¨α&2α12αΓα12¨ζpαq,where,asusual,ζpαq:°n1nα.
(iii)For0p¤1,PTνTtpu,vqTT:νTpST,u,vqpu$d2p1pqπp.
(iv)For12βV,PTνTpdvqTTpduqνTST,u,v¨¨β&212Γβ12¨Γpβq.
Proof.
(i)TherstequalityisclearfromthedenitionofRxpT,vqandFubini'stheorem.
Turningtotheequalityoftherstandlastterms,rstrecallthatPisthepush-forwardonpTwt,dGHwtqofthenormalizedexcursionmeasurePbythemapepT2e,dT2e,νT2eq,where2eU1isjusttheexcursionpatht2eptq.
Inparticular,T2eisthequotientoftheintervalr0,1sbytheequivalencerelationdenedby2e.
BytheinvarianceofthestandardBrownianexcursionunderrandomre-rooting(seeSection2.
7of[Ald91b]),thepointinT2ethatcorrespondstotheequivalenceclassof0r0,1sisdistributedaccordingtoνT2ewheneischosenaccordingtoP.
Moreover,recallfromtheendofSection3thatforeU1,thelengthmeasureTeisthepush-forwardofthemeasuredsda1spe,s,aqspe,s,aqδspe,s,aqonthesub-graphΓebythequotientmapdenedin(3.
2).
ItfollowsthatifwepickTaccordingtoPandthenpickpu,vqTTaccordingtoTνT,thenthesubtreeST,u,vthatariseshasthesameσ-nitelawasthetreeassociatedwiththeexcursion2es,awheneischo-senaccordingtoPandps,aqischosenaccordingtothemeasuredsda1spe,s,aqspe,s,aqδspe,s,aqonthesub-graphΓe.
SUBTREEPRUNEANDRE-GRAFT25Therefore,bypart(i)ofCorollary5.
3,PTνTpdvqTTpduq12heightpST,u,vqx@&2PpdeqΓedsdaspe,s,aqspe,s,aq14max0¤t¤ζpes,aqes,ax2B2Vn1nxexppn2x2{2q.
Part(ii)isaconsequenceofpart(i)andsomestraightforwardcalculus.
Part(iii)followsimmediatelyfrompart(ii)ofCorollary5.
3.
Part(iv)isaconsequenceofpart(iii)andsomemorestraightforwardcalculus.
6.
AsymmetricjumpmeasureonpTwt,dGHwtqInthissectionwewillconstructandstudyameasureonTwtTwtthatisrelatedtothedecompositiondiscussedatthebeginningofSection5.
DeneamapΘfromtppT,dq,u,vq:TT,uT,vTuintoTbysettingΘppT,dq,u,vq:pT,dpu,vqqwhereletting(6.
1)dpu,vqpx,yq:6998997dpx,yq,ifx,yST,u,v,dpx,yq,ifx,yTzST,u,v,dpx,uqdpv,yq,ifxST,u,v,yTzST,u,v,dpy,uqdpv,xq,ifyST,u,v,xTzST,u,v.
Thatis,ΘppT,dq,u,vqisjustTasaset,butthemetrichasbeenchangedsothatthesubtreeST,u,vwithrootuisnowprunedandre-graftedsoastohaverootv.
IfpT,d,νqTwtandpu,vqTT,thenwecanthinkofνasaweightonpT,dpu,vqq,becausetheBorelstructuresinducesbydanddpu,vqarethesame.
WithaslightmisuseofnotationwewillthereforewriteΘppT,d,νq,u,vqforpT,dpu,vq,νqTwt.
Intuitively,themasscontainedinST,u,vistransportedalongwiththesubtree.
DeneakernelκonTwtby(6.
2)κppT,dT,νTq,Bq:TνT2pu,vqTT:ΘpT,u,vqB@forBBpTwtq.
ThusκppT,dT,νTq,¤qisthejumpkerneldescribedinfor-mallyintheIntroduction.
Remark6.
1.
ItisclearthatκppT,dT,νTq,¤qisaBorelmeasureonTwtforeachpT,dT,νTqTwt.
Inordertoshowthatκp¤,BqisaBorelfunctiononTwtforeachBBpTwtq,sothatκisindeedakernel,itsucestoobserveforeachboundedcontinuousfunctionF:TwtRthatFpΘpT,u,vqqTpduqνTpdvqlimε0FpΘpT,u,vqqRεpTqpduqνTpdvq26STEVENN.
EVANSANDANITAWINTERandthatpT,dT,νTqFpΘpT,u,vqqRεpTqpduqνTpdvqiscontinuousforallε0(thelatterfollowsfromanargumentsimilartothatinLemma7.
3of[EPW04],whereitisshownthatthepT,dT,νTqRεpTqpTqiscontinuous).
Wehaveonlysketchedtheargumentthatκisakernel,becauseκisjustadevicefordeningthemeasureJonTwtTwtinthenextparagraph.
ItisactuallythemeasureJthatweusetodeneourDirichletform,andthemeasureJcanbeconstructeddirectlyasthepush-forwardofameasureonU1U1–seetheproofofLemma6.
2.
Weshowinpart(i)ofLemma6.
2belowthatthekernelκisreversiblewithrespecttotheprobabilitymeasureP.
Moreprecisely,weshowthatifwedeneameasureJonTwtTwtby(6.
3)JpABq:APpdTqκpT,BqforA,BBpTwtq,thenJissymmetric.
Lemma6.
2.
(i)ThemeasureJissymmetric.
(ii)ForeachcompactsubsetKTwtandopensubsetUsuchthatKUTwt,JpK,TwtzUqV.
(iii)ThefunctionGHwtissquare-integrablewithrespecttoJ,thatis,TwtTwtJpdT,dSq2GHwtpT,SqV.
Proof.
(i)GiveneI,ePU1,0¤u¤1,and0ρ¤1,deneep¤;eI,eP,u,ρqU1byept;eI,eP,u,ρq:S1ρePptq,0¤t¤p1ρqu,S1ρePpp1ρquqSρeIptp1ρquq,p1ρqu¤t¤p1ρquρ,S1ρePptρq,p1ρquρ¤t¤1.
(6.
4)Thatis,ep¤;eI,eP,u,ρqistheexcursionthatarisesfromBrownianre-scalingeIandePtohavelengthsρand1ρ,respectively,andtheninsertingthere-scaledversionofeIintothere-scaledversionofePatapositionthatisafractionuofthetotallengthofthere-scaledversionofeP.
SUBTREEPRUNEANDRE-GRAFT27DeneameasureJonU1U1byU1U1Jpde,deqKpe,eq:r0,1s2dudv122π10dρp1ρqρ3PpdeIqPpdePqKep¤;eI,eP,u,ρq,ep¤;eI,eP,v,ρq¨.
(6.
5)Clearly,themeasureJissymmetric.
Itfollowsfromthediscussionatthebeginningoftheproofofpart(i)ofLemma5.
4andCorollary5.
2thatthemeasureJisthepush-forwardofthesymmetricmeasure2JbythemapU1U1pe,eqppT2e,dT2e,νT2eq,pT2e,dT2e,νT2eqqTwtTwt,andhenceJisalsosymmetric.
(ii)TheresultistrivialifKr,soweassumethatKr.
SinceTwtzUandKaredisjointclosedsetsandKiscompact,wehavethat(6.
6)c:infTK,SUGHwtpT,Sq0.
FixTK.
Ifpu,vqTTissuchthatGHwtpT,ΘpT,u,vqqc,thendiampTqc(sothatwecanthinkofRcpTq,recall(2.
27),asasubsetofT).
Moreover,weclaimthateitheruRcpT,vq(recall(2.
26)),oruRcpT,vqandνTpST,u,vqc(recall(5.
17)).
Suppose,tothecontrary,thatuRcpT,vqandthatνTpST,u,ρq¤c.
BecauseuRcpT,vq,themapf:TΘpT,u,vqgivenbyfpwq:u,ifwST,u,v,w,otherwise.
isameasurablec-isometry.
Thereisananalogousmeasurablec-isometryg:ΘpT,u,vqT.
Clearly,dPpfνT,νΘpT,u,vqq¤canddPpνT,gνΘpT,u,vqq¤c.
Hence,bydenition,GHwtpT,ΘpT,u,vqq¤c.
28STEVENN.
EVANSANDANITAWINTERThuswehave(6.
7)JpK,TwtzUq¤KPtdTuκpT,tS:GHwtpT,Sqcuq¤KPpdTqTνTpdvqTpRcpT,vqqKPpdTqTνTpdvqTtuT:νTpST,u,vqcuV,wherewehaveusedLemma5.
4.
(iii)Similarreasoningyieldsthat(6.
8)TwtTwtJpdT,dSq2GHwtpT,SqTwtPtdTuV0dt2tκpT,tS:GHwtpT,Sqtuq¤TwtPpdTqV0dt2tTνTpdvqTpRcpT,vqqTwtPpdTqV0dt2tTνTpdvqTtuT:νTtST,u,vutu¤V0dt2tTwtPpdTqTνTpdvqTpRcpT,vqqTwtPpdTqTνTpdvqTTpduqν2TpST,u,vqV,wherewehaveappliedLemma5.
4oncemore.
7.
DirichletformsConsiderthebilinearform(7.
1)Epf,gq:TwtTwtJpdT,dSqfpSqfpTq¨gpSqgpTq¨,forf,ginthedomain(7.
2)DpEq:tfL2pTwt,Pq:fismeasurable,andEpf,fqVu,(hereasusual,L2pTwt,Pqisequippedwiththeinnerproductpf,gqP:Ppdxqfpxqgpxq).
BytheargumentinExample1.
2.
1in[FOT94]andLemma6.
2,pE,DpEqqiswell-dened,symmetricandMarkovian.
SUBTREEPRUNEANDRE-GRAFT29Lemma7.
1.
TheformpE,DpEqqisclosed.
Thatis,ifpfnqnNbease-quenceinDpEqsuchthatlimm,nVpEpfnfm,fnfmqpfnfm,fnfmqPq0,thenthereexistsfDpEqsuchthatlimnVpEpfnf,fnfqpfnf,fnfqPq0.
Proof.
LetpfnqnNbeasequencesuchthatlimm,nVEpfnfm,fnfmqpfnfm,fnfmqP0(thatis,pfnqnNisCauchywithrespecttoEp¤,¤qp¤,¤qP).
ThereexistsasubsequencepnkqkNandfL2pTwt,PqsuchthatlimkVfnkf,P-a.
s,andlimkVpfnkf,fnkfqP0.
ByFatou'sLemma,(7.
3)JpdT,dSqpfpSqfpTq¨2¤liminfkVEpfnk,fnkqV,andsofDpEq.
Similarly,(7.
4)Epfnf,fnfqJpdT,dSqlimkVpfnfnkqpSqpfnfnkqpTq¨2¤liminfkVEpfnfnk,fnfnkq0asnV.
ThuspfnqnNhasasubsequencethatconvergestofwithrespecttoEp¤,¤qp¤,¤qP,but,bytheCauchyproperty,thisimpliesthatpfnqnNitselfconvergestof.
LetLdenotethecollectionoffunctionsf:TwtRsuchthat(7.
5)supTTwt|fpTq|Vand(7.
6)supS,TTwt,ST|fpSqfpTq|GHwtpS,TqV.
NotethatLconsistsofcontinuousfunctionsandcontainstheconstants.
Itfollowsfrom(2.
16)thatLisbothavectorlatticeandanalgebra.
ByLemma7.
2below,LDpEq.
Therefore,theclosureofpE,LqisaDirichletformthatwewilldenotebypE,DpEqq.
Lemma7.
2.
SupposethattfnunNisasequenceoffunctionsfromTwtintoRsuchthatsupnNsupTTwt|fnpTq|V,supnNsupS,TTwt,ST|fnpSqfnpTq|GHwtpS,TqV,30STEVENN.
EVANSANDANITAWINTERandlimnVfnf,P-a.
s.
forsomef:TwtR.
ThentfnunNDpEq,fDpEq,andlimnVpEpfnf,fnfqpfnf,fnfqPq0.
Proof.
BythedenitionofthemeasureJ(see(6.
3))andthesymmetryofJ(Lemma6.
2(i)),wehavethatfnpxqfnpyqfpxqfpyqforJ-almosteverypairpx,yq.
Theresultthenfollowsfrompart(iii)ofLemma6.
2andthedominatedconvergencetheorem.
BeforeshowingthatpE,DpEqqistheDirichletformofaniceMarkovprocess,weremarkthatL,andhenceDpEqisquitearichclassoffunctions:weshowintheproofofTheorem7.
3belowthatLseparatespointsofTwtandhenceifKisanycompactsubsetofTwt,then,bytheArzela-Ascolitheorem,thesetofrestrictionsoffunctionsinLtoKisuniformlydenseinthespaceofreal-valuedcontinuousfunctionsonK.
Thefollowingtheoremstatesthatthereisawell-denedMarkovprocesswiththedynamicswewouldexpectforalimitofthesubtreepruneandre-graftchains.
Theorem7.
3.
ThereexistsarecurrentP-symmetricHuntprocessXpXt,PTqonTwtwhoseDirichletformispE,DpEqq.
Proof.
WewillchecktheconditionsofTheorem7.
3.
1in[FOT94]toestablishtheexistenceofX.
BecauseTwtiscompleteandseparable(recallTheorem2.
5)thereisasequenceH1H2.
.
.
ofcompactsubsetsofTwtsuchthatPpkNHkq1.
Givenα,β0,writeLα,βforthesubsetofLconsistingoffunctionsfsuchthat(7.
7)supTTwt|fpTq|¤αand(7.
8)supS,TTwt,ST|fpSqfpTq|GHwtpS,Tq¤β.
Bytheseparabilityofthecontinuousreal-valuedfunctionsoneachHkwithrespecttothesupremumnorm,itfollowsthatforeachkNthereisacountablesetLα,β,kLα,βsuchthatforeveryfLα,β(7.
9)infgLα,β,ksupTHk|fpTqgpTq|0.
SetLα,β:kNLα,β,k.
ThenforanyfLα,βthereexistsasequencetfnunNinLα,βsuchthatlimnVfnfpointwiseonkNHk,andhenceP-almostsurely.
ByLemma7.
2,thecountablesetmNLm,misdenseinL,andhencealsodenseinDpEq,withrespecttoEp¤,¤qp¤,¤qP.
SUBTREEPRUNEANDRE-GRAFT31NowxacountabledensesubsetSTwt.
LetMdenotethecountablesetoffunctionsoftheform(7.
10)TpqpGHwtpS,TqrqforsomeSSandp,q,rQ.
NotethatML,thatMseparatesthepointsofTwt,and,foranyTTwt,thatthereiscertainlyafunctionfMwithfpTq0.
Consequently,ifCisthealgebrageneratedbythecountablesetMmNLm,m,thenitiscertainlythecasethatCisdenseinDpEqwithrespectEp¤,¤qp¤,¤qP,thatCseparatesthepointsofTwt,and,foranyTTwt,thatthereisafunctionfCwithfpTq0.
AllthatremainsinverifyingtheconditionsofTheorem7.
3.
1in[FOT94]istocheckthetightnessconditionthatthereexistcompactsubsetsK1K2.
.
.
ofTwtsuchthatlimnVCappTwtzKnq0whereCapisthecapacityassociatedwiththeDirichletform–seeRemark7.
4belowforadenition.
Thisconvergence,however,isthecontentofLemma7.
7below.
Finally,becauseconstantsbelongstoDpEq,itfollowsfromTheorem1.
6.
3in[FOT94]thatXisrecurrent.
Remark7.
4.
IntheproofofTheorem7.
3weusedthecapacityassociatedwiththeDirichletformpE,DpEqq.
WeremindthereaderthatforanopensubsetUTwt,CappUq:inftEpf,fqpf,fqP:fDpEq,fpTq1,Pa.
e.
TUu,andforageneralsubsetATwtCappAq:inftCappUq:AUisopenu.
WereferthereadertoSection2.
1of[FOT94]fordetailsandaproofthatCapisaChoquetcapacity.
ThefollowingresultswereneededintheproofofTheorem7.
3Lemma7.
5.
Forε,a,δ0,putVε,a:tTT:TpRεpTqqauand,asusual,Vδε,a:tTT:dGHpT,Vε,aqδu.
Then,forxedε3δ,a0Vδε,ar.
Proof.
FixST.
IfSVδε,a,thenthereexistsTVε,asuchthatdGHpS,Tqδ.
ObservethatRεpTqisnotthetrivialtreeconsistingofasinglepointbecauseithastotallengthgreaterthana.
Writety1,ynufortheleavesofRεpTq.
Foralli1,.
.
.
,n,theconnectedcomponentofTzRεpTqothatcontainsyicontainsapointzisuchthatdTpyi,ziqε.
LetbeacorrespondencebetweenSandTwithdispq2δ.
Pickx1,xnSsuchthatpxi,ziq,andhence|dSpxi,xjqdTpzi,zjq|2δforalli,j.
32STEVENN.
EVANSANDANITAWINTERThedistanceinRεpTqfromthepointyktothearcryi,yjsis(7.
11)12dSpyk,yiqdSpyk,yjqdSpyi,yjq¨.
Thusthedistancefromyk,3¤k¤n,tothesubtreespannedbyy1,yk1is(7.
12)1¤i¤j¤k112dTpyk,yiqdTpyk,yjqdTpyi,yjq¨,andhenceTpRεpTqqdTpy1,y2qnk31¤i¤j¤k112pdTpyk,yiqdTpyk,yjqdTpyi,yjqq.
(7.
13)NowthedistanceinSfromthepointxktothearcrxi,xjsis12pdSpxk,xiqdSpxk,xjqdSpxi,xjqq12pdTpzk,ziqdTpzk,zjqdTpzi,zjq32δq12pdTpyk,yiq2εdTpyk,yjq2εdTpyi,yjq2ε6δq0(7.
14)bytheassumptionthatε3δ.
Inparticular,x1,xnareleavesofthesubtreespannedbytx1,xnu,andRγpSqhasatleastnleaveswhen0γ2ε6δ.
Fixsuchaγ.
NowSpRγpSqqdSpx1,x2q2γnk31¤i¤j¤k112pdSpxk,xiqdSpxk,xjqdSpxi,xjqqγ&TpRεpTqqp2ε2δ2γqpn2qpε3δγqap2ε2δ2γqpn2qpε3δγq.
(7.
15)BecauseSpRγpSqqisnite,itisapparentthatScannotbelongtoVδε,awhenaissucientlylarge.
Lemma7.
6.
Forε,a0,letVε,abeasinLemma7.
5.
SetUε,a:tpT,νqTwt:TVε,au.
Then,forxedε,(7.
16)limaVCappUε,aq0.
SUBTREEPRUNEANDRE-GRAFT33Proof.
ObservethatpT,dT,νTqRεpTqpTqiscontinuous(thisisessentiallyLemma7.
3of[EPW04]),andsoUε,aisopen.
Chooseδ0suchthatε3δ.
Suppressingthedependenceonεandδ,deneua:Twtr0,1sby(7.
17)uappT,νqq:δ1pδdGHpT,Vε,aqq.
Notethatuatakesthevalue1ontheopensetUε,a,andsoCappUε,aq¤Epua,uaqpua,uaqP.
Alsoobservethat(7.
18)|uappTI,νIqquappTP,νPqq|¤δ1dGHpTI,TPq¤δ1GHwtppTI,νIq,pTP,νPqq.
Itthereforesucesbypart(iii)ofLemma6.
2andthedominatedcon-vergencetheoremtoshowforeachpairppTI,νIq,pTP,νPqqTwtTwtthatuappTI,νIqquappTP,νPqqis0forasucientlylargeandforeachTTwtthatuappT,νqqis0forasucientlylarge.
However,uappTI,νIqquappTP,νPqq0impliesthateitherTIorTPbelongtoVδε,a,whileuappT,νqq0impliesthatTbelongstoVδε,a.
TheresultthenfollowsfromLemma7.
5.
Lemma7.
7.
ThereisasequenceofcompactsetsK1K2.
.
.
suchthatlimnVCappTwtzKnq0.
Proof.
ByLemma7.
6,forn1,2,.
.
.
wecanchooseansothatCappU2n,anq¤2n.
Set(7.
19)Fn:TwtzU2n,antpT,νqTwt:TpR2npTqq¤anuand(7.
20)Kn:mnFm.
ByProposition2.
4andLemma2.
6,eachsetKniscompact.
Byconstruc-tion,CappTwtzKnqCap¤mnU2m,am¤mnCappU2m,amq¤mn2m2pn1q.
(7.
21)34STEVENN.
EVANSANDANITAWINTER8.
ThetrivialtreeisessentiallypolarFromourinformalpictureoftheprocessXevolvingviare-arrangementsoftheinitialtreethatpreservethetotalbranchlength,onemightexpectthatifXdoesnotstartatthetrivialtreeT0consistingofasinglepoint,thenXwillneverhitT0.
However,anSPRmovecandecreasethediameterofatree,soitisconceivablethat,inpassingtothelimit,thereissomeprobabilitythataninnitesequenceofSPRmoveswillconspiretocollapsetheevolvingtreedowntoasinglepoint.
Ofcourse,itishardtoimaginefromtheapproximatingdynamicshowXcouldrecoverfromsuchacatastrophe–whichitwouldhavetosinceitisreversiblewithrespecttothecontinuumrandomtreedistribution.
InthissectionwewillusepotentialtheoryforDirichletformstoshowthatXdoesnothitT0fromP-almostallstartingpoints;thatis,thatthesettT0uisessentiallypolar.
LetdbethemapwhichsendsaweightedRtreepT,d,νqtotheν-averageddistancebetweenpairsofpointsinT.
Thatis,(8.
1)dpT,d,νq¨:TTνpdxqνpdyqdpx,yq,pT,d,νqTwt.
InordertoshowthatT0isessentiallypolar,itwillsucetoshowthattheset(8.
2)tpT,d,νqTwt:dpT,d,νq¨0uisessentiallypolar.
Lemma8.
1.
ThefunctiondbelongstothedomainDpEq.
Proof.
IfweletdnpT,d,νq¨:TTνpdxqνpdyqrdpx,yqns,fornN,thendnd,P-a.
s.
Bythetriangleinequality,(8.
3)pd,dqP¤PpdTqpdiampTqq2¤Ppdeq4suptr0,1septq¨2V,andhencedndasnVinL2pTwt,Pq.
Notice,moreover,thatforpT,d,νqTwtandu,vT,(8.
4)dpT,d,νq¨dΘppT,d,νq,u,vq¨22ST,u,vTzST,u,vνpdxqνpdyqdpy,uqdpy,vq¨22νTpST,u,vqνpTzST,u,vqd2pu,vq.
SUBTREEPRUNEANDRE-GRAFT35Hence,applyingCorollary5.
2andtheinvarianceofthestandardBrownianexcursionunderrandomre-rooting(seeSection2.
7of[Ald91b]),(8.
5)TwtTwtJpdT,dSqdpTqdpSq¨22TwtPpdTqTTνTpdvqTpduqνTpST,u,vqνTpTzST,u,vqd2Tpu,vq¤2Ppdeq2Γedsdaspe,s,aqspe,s,aqζpes,aqζpˇes,aqp2aq282π10dρp1ρqρ3PpdeIqPpdePqρp1ρqsupS1ρeP¨282π10dρp1ρqρ3ρp1ρq2Ppdeqsuptr0,1septq2V.
Consequently,bydominatedconvergence,Epddn,ddnq0asnV.
ItisthereforeenoughtoverifythatdnLforallnN.
Obviously,(8.
6)supTTwtdnpTq¤n,andsotheboundednesscondition(7.
5)holds.
Toshowthatthe"Lipschitz"property(7.
6)holds,xε0,andletpT,νTq,pS,νSqTwtbesuchthatGHwtpT,νTq,pS,νSq¨ε.
ThenthereexistfFεT,SandgFεS,TsuchthatdPpνT,gνSqεanddPpfνT,νSqε(recallFεT,Sfrom(2.
10)).
Hence(8.
7)§§§§dnpT,νTq¨dnpS,νSq¨§§§§¤§§§§TTνTpdxqνTpdyqpdTpx,yqnqgpSqgpSqgνSpdxqgνSpdyqpdTpx,yqnq§§§§§§§§gpSqgpSqgνSpdxqgνSpdyqpdTpx,yqnqSSνSpdxIqνSpdyIqpdSpxI,yIqnq§§§§.
36STEVENN.
EVANSANDANITAWINTERForthersttermontherighthandsideof(8.
7)weget(8.
8)§§§§TTνTpdxqνTpdyqpdTpx,yqnqgpSqgpSqgνSpdxqgνSpdyqpdTpx,yqnq§§§§¤§§§§TTνTpdxqνTpdyqpdTpx,yqnqTgpSqνTpdxqgνSpdyqpdTpx,yqnq§§§§§§§§SpgqTgνSpdxqνTpdyqpdTpx,yqnqgpSqgpSqgνSpdxqgνSpdyqpdTpx,yqnq§§§§.
ByassumptionandTheorem3.
1.
2in[EK86],wecanndaprobabilitymeasureνonTTwithmarginalsνTandgνSsuchthat(8.
9)ν2px,yq:dTpx,yqε@¤ε.
Hence,forallxT,(8.
10)§§§§TνTpdyqpdTpx,yqnqgpSqgνSpdyqpdTpx,yqnq§§§§¤TgpSqνdpy,yIq¨§§§§pdTpx,yqnqpdTpx,yIqnq§§§§¤TgpSqνdpy,yIq¨pdTpy,yIqnq¤1pdiampTqnq¨¤ε.
Forthesecondtermin(8.
7)weusethefactthatgisanε-isometry,thatis,|pdSpxI,yIqnqpdTpgpxIq,gpyIqqnq|εforallxI,xPT.
Achangeofvariablesthenyieldsthat(8.
11)§§§§gpSqgpSqgνSpdxqgνSpdyqpdTpx,yqnqSSνSpdxIqνSpdyIqpdSpxI,yIqnq§§§§¤ε§§§§gpSqgpSqgνSpdxqgνSpdyqpdTpx,yqnqSSνSpdxIqνSpdyIqpdTpgpxIq,gpyIqqnq§§§§ε.
SUBTREEPRUNEANDRE-GRAFT37Combining(8.
7)through(8.
11)yieldsnallythat(8.
12)suppT,νTqpS,νSqTwt§§dnpT,νTq¨dnpS,νSq¨§§GHwtpT,νTq,pS,νSq¨¤32n.
Proposition8.
2.
ThesettTTwt:dpTq0uisessentiallypolar.
Inparticular,thesettT0uconsistingofthetrivialtreeisessentiallypolar.
Proof.
WeneedtoshowthatCapptTTwt:dpTq0uq0(seeTheorem4.
2.
1of[FOT94]).
Forε0set(8.
13)Wε:tTTwt:dpTqεu.
BytheargumentintheproofofLemma8.
1,thefunctiondiscontinuous,andsoWεisopen.
ItsucestoshowthatCappWεq0asε0.
Put(8.
14)uεpTq:2dpTqε,TTwt.
ThenuDpEqbyLemma8.
1andthefactthatthedomainofaDirichletformisclosedundercompositionwithLipschitzfunctions.
BecauseuεpTq1forTWε,itthusfurthersucestoshow(8.
15)limε0pEpuε,uεqpuε,uεqPq0.
ByelementarypropertiesofthestandardBrownianexcursion,(8.
16)puε,uεqP¤4PtT:dpTq2εu0asε0.
EstimatingEpuε,uεqwillbesomewhatmoreinvolved.
LetEandˇEbetwoindependentstandardBrownianexcursions,andletUandVbetwoindependentrandomvariablesthatareindependentofEandˇEanduniformlydistributedonr0,1s.
Withaslightabuseofnotation,wewillwritePfortheprobabilitymeasureontheprobabilityspacewhereE,ˇE,UandVaredened.
38STEVENN.
EVANSANDANITAWINTERSetD:40¤st¤1dsdtEsEt2infs¤w¤tEw&H:2r0,1sdtEtˇD:40¤st¤1dsdtˇEsˇEt2infs¤w¤tˇEw&ˇHU:2r0,1sdtˇEtˇEU2infUt¤w¤UtˇEw&ˇHV:2r0,1sdtˇEtˇEV2infVt¤w¤VtˇEw&.
(8.
17)For0¤ρ¤1setDUpρq:p1ρq21ρˇDρ2ρD2p1ρqρρH2p1ρqρ1ρˇHU(8.
18)andDVpρq:p1ρq21ρˇDρ2ρD2p1ρqρρH2p1ρqρ1ρˇHV.
(8.
19)ThenEpuε,uεq122πP10dρp1ρqρ342DUpρqε2DVpρqεB2'.
(8.
20)Fix0a12andwritea1aforconvenience.
Wecanwritetheright-handsideof(8.
20)asthesumofthreetermsIpε,aq,IIpε,aq,andIIIpε,aq,thatarisefromintegratingρovertherespectiveranges(8.
21)tρ:DUpρqDVpρq¤2ε,0¤ρ¤au,(8.
22)tρ:DUpρqDVpρq¤2ε¤DUpρqDVpρq,0¤ρ¤au,and(8.
23)tρ:aρ¤1u.
ConsiderIpε,aqrst.
NotethatifDUpρqDVpρq¤2ε,then(8.
24)42DUpρqε2DVpρqεB2¤22ρ2ε2tˇHUˇHVu2.
SUBTREEPRUNEANDRE-GRAFT39Moreover,t0¤ρ¤a:DUpρqDVpρq¤2εu30¤ρ¤a:p1ρq52ˇD2p1ρq32ρpˇHUˇHVq¤2εA30¤ρ¤a:a52ˇD2a32ρpˇHUˇHVq¤2εA5ρ:0¤ρ¤p2εa52ˇDq2a32pˇHUˇHVqaC.
(8.
25)ThusIpε,aqisboundedabovebytheexpectationoftherandomvariablethatarisesfromintegrating22ρ2tˇHUˇHVu2{ε2againstthemeasure12`2πdρp1ρqρ3overtheintervalr0,p2εa52ˇDq{p2a32pˇHUˇHVqqs.
Notethat(8.
26)x0dρρ3ρα1α12xα12,α12.
Hence,lettingCdenoteagenericconstantwithavaluethatdoesn'tdependonεoraandmaychangefromlinetoline,andIpε,aq¤CP!
p2εa52ˇDqˇHUˇHV32tˇHUˇHVu2ε2()¤Cε2Pp2εa52ˇDq32pˇHUˇHVq12&¤Cε12PpˇHUˇHVq121tˇD¤2a52εu%¤Cε12PˇD121tˇD¤2a52εu%¤CPtˇD¤2a52εu,(8.
27)whereinthesecondlastlineweusedthefactthat(8.
28)PrˇHU|ˇEsPrˇHV|ˇEsˇD,andJensen'sinequalityforconditionalexpectationstoobtaintheinequali-tiesPrˇH12U|ˇEs¤ˇD12andPrˇH12V|ˇEs¤ˇD12.
Thus,limε0Ipε,aq0foranyvalueofa.
TurningtoIIpε,aq,rstnotethatD¤4Hand,bythetriangleinequality,(8.
29)ˇD¤2pˇHUˇHVq.
Hence,forsomeconstantKthatdoesnotdependonεora,(8.
30)|DUpρqDVpρqˇD|¤KpHρ32pˇHUˇHVqρqand(8.
31)|DUpρqDVpρqˇD|¤KpHρ32pˇHUˇHVqρq.
40STEVENN.
EVANSANDANITAWINTERCombining(8.
31)withanargumentsimilartothatwhichestablished(8.
25)gives,forasuitableconstantK,t0¤ρ¤a:DUpρqDVpρq¤2ε¤DUpρqDVpρqut0¤ρ¤a:2ε¤DUpρqDVpρq,ut0¤ρ¤a:DUpρqDVpρq¤2εu5ρ:p2εˇDqKpHˇHUˇHVq¤ρ¤aC5ρ:0¤ρ¤p2εa52ˇDq2a32pˇHUˇHVqaC.
(8.
32)Moreover,by(8.
30)andtheobservation|p2εxqp2εyq|¤|xy|,wehaveforDUpρqDVpρq¤2ε¤DUpρqDVpρqthat,42DUpρqε2DVpρqεB242DUpρqDVpρqεB2¤2ε232εˇD¨A22ε23p2εDUpρqDVpρqq2εˇD¨A2¤2ε232εˇD¨A22ε22DUpρqDVpρqˇD@2¤Cε2p2εˇDq2H2ρ3pˇHUˇHVq2ρ2%.
(8.
33)forasuitableconstantCthatdoesn'tdependonεora.
Itfollowsfrom(8.
26)and(8.
34)axdρρ3ρβ112βxβ12aβ12%,β12,thatIIpε,aq¤CIε2P!
p2εˇDq24p2εˇDqHˇHUˇHVB12()CPε2P!
H25p2εa52ˇDq2a32pˇHUˇHVqaC52()CQε2P!
pˇHUˇHVq25p2εa52ˇDq2a32pˇHUˇHVqaC32()(8.
35)forsuitableconstantsCI,CP,andCQ.
SUBTREEPRUNEANDRE-GRAFT41Considerthersttermin(8.
35).
UsingJensen'sinequalityforconditionalexpectationsand(8.
28)again,thistermisboundedaboveby(8.
36)1ε2Pp2εˇDq323AˇD12BA&¤1ε2Pp2εˇDq323212Aε12BA&forsuitableconstantsA,B.
Now,byJensen'sinequalityforconditionalexpectationyetagain,alongwiththeinvarianceofstandardBrownianex-cursionunderrandomre-rooting(seeSection2.
7of[Ald91b])andthefactthat(8.
37)PtˇEUdrurer22dr(seeSection3.
3of[Ald91b]),wehavePp2εˇDq32&PP2ε24ˇEUˇEV2infUV¤t¤UVˇEtB§§§ˇE&32'¤P2ε24ˇEUˇEV2infUV¤t¤UVˇEtB32'P2ε2ˇEU¨32%V0drrer22p2ε2rq32¤ε0drrp2ε2rq32232ε7210dssp1sq32.
(8.
38)Thusthelimitasε0ofthersttermin(8.
35)is0foreacha.
Forthesecondtermin(8.
35),rstobservebyJensen'sinequalityforconditionalexpectationand(8.
37)thatPtˇD¤ru¤P2ˇDr&¤P2ˇEUr&¤2P2ˇEU¤2r@¤2p2rq224r2.
(8.
39)42STEVENN.
EVANSANDANITAWINTERCombiningthisobservationwith(8.
29)andintegratingbypartsgivesP!
5p2εa52ˇDq2a32pˇHUˇHVqaC52()¤P!
5p2εa52ˇDqa32ˇDaC52()2ε{a520PtˇDdrua322εra52a52¤2ε{a522ε{paa12a52qdr4r2a154522εra52322εr240ε2a1541{a521{paa12a52qds1sa5232.
(8.
40)IfwedenotetherightmosttermbyLpε,aq,thenitisclearthat(8.
41)lima0limε01ε2Lpε,aq0.
From(8.
28)andJensen'sinequalityforconditionalexpectations,thethirdtermin(8.
35)isboundedabovebyCε2PpˇHUˇHVq122εa52ˇD32&¤Cε2PˇD122εa52ˇD32&¤Cε32P2εa52ˇD32&,(8.
42)andthecalculationin(8.
38)showsthattherightmosttermconvergestozeroasε0foreacha.
Puttingtogethertheobservationswehavemadeonthethreetermsin(8.
35),weseethat(8.
43)lima0limε0IIpε,aq0.
Itfollowsfromthedominatedconvergencetheoremthat(8.
44)limε0IIIpε,aq0foralla,andthiscompletestheproof.
AcknowledgmentTheauthorsthankDavidAldous,PeterPfaelhuber,JimPitmanandTandyWarnowforhelpfuldiscussions,andtherefereeandassociateeditorforextremelyclosereadingsofthepaperandseveralveryhelpfulsuggestions.
PartoftheresearchwasconductedwhiletheauthorsSUBTREEPRUNEANDRE-GRAFT43werevisitingthePacicInstitutefortheMathematicalSciencesinVancou-ver,Canada.
References[Ald91a]DavidAldous.
ThecontinuumrandomtreeI.
Ann.
Probab.
,19:1–28,1991.
[Ald91b]DavidAldous.
Thecontinuumrandomtree.
II.
Anoverview.
InStochasticanalysis(Durham,1990),volume167ofLondonMath.
Soc.
LectureNoteSer.
,pages23–70.
CambridgeUniv.
Press,Cambridge,1991.
[Ald93]DavidAldous.
ThecontinuumrandomtreeIII.
Ann.
Probab.
,21:248–289,1993.
[Ald00]DavidJ.
Aldous.
MixingtimeforaMarkovchainoncladograms.
Combin.
Probab.
Comput.
,9(3):191–204,2000.
[AS01]BenjaminL.
AllenandMikeSteel.
Subtreetransferoperationsandtheirin-ducedmetricsonevolutionarytrees.
Ann.
Comb.
,5(1):1–15,2001.
[AS02]RomainAbrahamandLaurentSerlet.
Poissonsnakeandfragmentation.
Elec-tron.
J.
Probab.
,7:no.
17,15pp.
(electronic),2002.
[BBI01]DmitriBurago,YuriBurago,andSergeiIvanov.
Acourseinmetricgeometry,volume33ofGraduatestudiesinmathematics.
AMS,Boston,MA,2001.
[Ber96]JeanBertoin.
Levyprocesses,volume121ofCambridgeTractsinMathematics.
CambridgeUniversityPress,Cambridge,1996.
[BH99]MartinR.
BridsonandAndreHaeiger.
Metricspacesofnon-positivecurva-ture,volume319ofGrundlehrenderMathematischenWissenschaften[Funda-mentalPrinciplesofMathematicalSciences].
Springer-Verlag,Berlin,1999.
[BHV01]LouisJ.
Billera,SusanP.
Holmes,andKarenVogtmann.
Geometryofthespaceofphylogenetictrees.
Adv.
inAppl.
Math.
,27(4):733–767,2001.
[BRST02]OliverBastert,DanRockmore,PeterF.
Stadler,andGottfriedTinhofer.
Land-scapesonspacesoftrees.
Appl.
Math.
Comput.
,131(2-3):439–459,2002.
[Chi01]IanChiswell.
IntroductiontoΛ-trees.
WorldScienticPublishingCo.
Inc.
,RiverEdge,NJ,2001.
[DH02]PersiDiaconisandSusanP.
Holmes.
Randomwalksontreesandmatchings.
Electron.
J.
Probab.
,7:no.
6,17pp.
(electronic),2002.
[DLG02]ThomasDuquesneandJean-FrancoisLeGall.
Randomtrees,Levyprocessesandspatialbranchingprocesses.
Asterisque,(281):vi+147,2002.
[DMT96]AndreasW.
M.
Dress,V.
Moulton,andW.
F.
Terhalle.
T-theorie.
Europ.
J.
Combinatorics,17,1996.
[Dre84]AndreasW.
M.
Dress.
Trees,tightextensionsofmetricspaces,andthecoho-mologicaldimensionofcertaingroups:Anoteoncombinatoricalpropertiesofmetricspaces.
Adv.
Math.
,53:321–402,1984.
[DT96]AndreasW.
M.
DressandW.
F.
Terhalle.
Therealtree.
Adv.
Math.
,120:283–301,1996.
[DVJ88]D.
J.
DaleyandD.
Vere-Jones.
Anintroductiontothetheoryofpointprocesses.
SpringerSeriesinStatistics.
Springer-Verlag,NewYork,1988.
[EK86]StewartN.
EthierandThomasG.
Kurtz.
Markovprocesses.
WileySeriesinProbabilityandMathematicalStatistics:ProbabilityandMathematicalSta-tistics.
JohnWiley&SonsInc.
,NewYork,1986.
Characterizationandconver-gence.
[EPW04]StevenN.
Evans,JimPitman,andAnitaWinter.
Rayleighprocesses,realtrees,androotgrowthwithre-grafting.
TechnicalReport654,U.
C.
BerkeleyDepartmentofStatistics,2004.
ToappearinProbabilityTheoryandRelatedFields.
[Fel03]JosephFelsenstein.
InferringPhylogenies.
SinauerAssociates,Sunderland,Massachusetts,2003.
44STEVENN.
EVANSANDANITAWINTER[FOT94]MasatoshiFukushima,YoichiOshima,andMasayoshiTakeda.
DirichletFormsandSymmetricMarkovProcesses.
deGruyter,1994.
[Gro99]MishaGromov.
MetricstructuresforRiemannianandnon-Riemannianspaces,volume152ofProgressinMathematics.
Birkh¨auserBostonInc.
,Boston,MA,1999.
Basedonthe1981Frenchoriginal[MR85e:53051],WithappendicesbyM.
Katz,P.
PansuandS.
Semmes,TranslatedfromtheFrenchbySeanMichaelBates.
[Kel75]JohnL.
Kelley.
Generaltopology.
Springer-Verlag,NewYork,1975.
Reprintofthe1955edition[VanNostrand,Toronto,Ont.
],GraduateTextsinMathemat-ics,No.
27.
[Kni81]FrankB.
Knight.
EssentialsofBrownianmotionanddiusion,volume18ofMathematicalSurveys.
AmericanMathematicalSociety,Providence,R.
I.
,1981.
[LG99]Jean-FrancoisLeGall.
Spatialbranchingprocesses,randomsnakesandpartialdierentialequations.
LecturesinMathematicsETHZ¨urich.
Birkh¨auserVerlag,Basel,1999.
[RW00]L.
C.
G.
RogersandDavidWilliams.
Diusions,Markovprocesses,andmartin-gales.
Vol.
2.
CambridgeMathematicalLibrary.
CambridgeUniversityPress,Cambridge,2000.
Itocalculus,Reprintofthesecond(1994)edition.
[RY99]DanielRevuzandMarcYor.
ContinuousmartingalesandBrownianmotion,volume293ofGrundlehrenderMathematischenWissenschaften[FundamentalPrinciplesofMathematicalSciences].
Springer-Verlag,Berlin,thirdedition,1999.
[Sch02]JasonSchweinsberg.
AnOpn2qboundfortherelaxationtimeofaMarkovchainoncladograms.
RandomStructuresAlgorithms,20(1):59–70,2002.
[SO90]D.
L.
SwoordandG.
J.
Olsen.
Phylogenyreconstruction.
InD.
M.
HillisandG.
Moritz,editors,MolecularSystematics,pages411–501.
SinauerAssociates,Sunderland,Massachusetts,1990.
[SS03]CharlesSempleandMikeSteel.
Phylogenetics,volume24ofOxfordLectureSeriesinMathematicsanditsApplications.
OxfordUniversityPress,Oxford,2003.
[Stu04]Karl-TheodorSturm.
Onthegeometryofmetricmeasurespaces.
TechnicalReport203,SFB611,Universit¨atBonn,2004.
[Ter97]W.
F.
Terhalle.
R-treesandsymmetricdierencesofsets.
Europ.
J.
Combina-torics,18:825–833,1997.
[Zam01]LorenzoZambotti.
Areectedstochasticheatequationassymmetricdynamicswithrespecttothe3-dBesselbridge.
J.
Funct.
Anal.
,180(1):195–209,2001.
[Zam02]LorenzoZambotti.
IntegrationbypartsonBesselbridgesandrelatedstochasticpartialdierentialequations.
C.
R.
Math.
Acad.
Sci.
Paris,334(3):209–212,2002.
[Zam03]LorenzoZambotti.
Integrationbypartsonδ-Besselbridges,δ3andrelatedSPDEs.
Ann.
Probab.
,31(1):323–348,2003.
StevenN.
Evans,DepartmentofStatistics#3860,UniversityofCaliforniaatBerkeley,367EvansHall,Berkeley,CA94720-3860,U.
S.
A.
E-mailaddress:evans@stat.
Berkeley.
EDUURL:http://www.
stat.
berkeley.
edu/users/evans/AnitaWinter,MathematischesInstitut,Universit¨atErlangen–N¨urnberg,Bismarckstrae112,91054Erlangen,GERMANYE-mailaddress:winter@mi.
uni-erlangen.
deURL:http://www.
mi.
uni-erlangen.
de/~winter/