The Directed Spanning Forest is almost surely a tree

David Coupier

Description

Niveau: Supérieur, Doctorat, Bac+8
The Directed Spanning Forest is almost surely a tree David Coupier, Viet Chi Tran January 31, 2011 Abstract We consider the Directed Spanning Forest (DSF) constructed as follows: given a Poisson point process N on the plane, the ancestor of each point is the nearest vertex of N having a strictly larger abscissa. We prove that the DSF is actually a tree. Contrary to other directed forests of the literature, no Markovian process can be introduced to study the paths in our DSF. Our proof is based on a comparison argument between surface and perimeter from percolation theory. We then show that this result still holds when the points of N belonging to an auxiliary Boolean model are removed. Using these results, we prove that there is no bi-infinite paths in the DSF. 2 Keywords: Stochastic geometry; Directed Spanning Forest; Percolation. AMS Classification: 60D05 1 Introduction Let us consider a homogeneous Poisson point process N (PPP) on R2 with intensity 1. The plane R2 is equipped with its canonical orthonormal basis (O, ex, ey) where O denotes the origin (0, 0). In the sequel, the ex and ey coordinates of any given point of R2 are respectively called its abscissa and its ordinate, and often denoted by (x, y). From the PPP N , Baccelli and Bordenave [3] defined the Directed Spanning Forest (DSF) with direction ex as a random graph whose vertex set is N and whose edge set satisfies: the ancestor of a point X ? N is the

• dsf


• introduction let


• radius √


• let n?


• directed spanning


• infinite paths


• there exists

Sujets

• Existential quantification

Informations

• Publié par: mijec
• Nombre de lectures: 9
• Langue: English

Extrait

TheDirectedSpanningForestisalmostsurelyatree DavidCoupier,VietChiTran January31,2011 Abstract WeconsidertheDirectedSpanningForest(DSF)constructedasfollows:givenaPoisson pointprocessNontheplane,theancestorofeachpointisthenearestvertexofNhavinga strictlylargerabscissa.WeprovethattheDSFisactuallyatree.Contrarytootherdirected forestsoftheliterature,noMarkovianprocesscanbeintroducedtostudythepathsinour DSF.Ourproofisbasedonacomparisonargumentbetweensurfaceandperimeterfrom percolationtheory.WethenshowthatthisresultstillholdswhenthepointsofNbelonging toanauxiliaryBooleanmodelareremoved.Usingtheseresults,weprovethatthereisno bi-infinitepathsintheDSF. ✷ Keywords:Stochasticgeometry;DirectedSpanningForest;Percolation. AMSClassification:60D05 1Introduction LetusconsiderahomogeneousPoissonpointprocessN(PPP)on R 2 withintensity1.The plane R 2 isequippedwithitscanonicalorthonormalbasis(O,e x ,e y )whereOdenotestheorigin (0,0).Inthesequel,thee x ande y coordinatesofanygivenpointof R 2 arerespectivelycalled itsabscissaanditsordinate,andoftendenotedby(x,y). FromthePPPN,BaccelliandBordenave[3]definedtheDirectedSpanningForest(DSF)with directione x asarandomgraphwhosevertexsetisNandwhoseedgesetsatisfies:theancestor ofapointX ∈ NisthenearestpointofNhavingastrictlylargerabscissa.Intheirpaper, theDSFappearsasanessentialtoolfortheasymptoticanalysisoftheRadialSpanningTree (RST).Indeed,theDSFcanbeseenasthelimitoftheRSTfarawayfromitsroot. EachvertexXoftheDSFalmostsurely(a.s.)hasauniqueancestor(butmayhaveseveral children).So,theDSFcanhavenoloop.Thisisaforest,i.e.aunionofoneormoredisjoint trees.ThemostnaturalquestiononemightaskabouttheDSFiswhethertheDSFisatree. Theansweris“yes”withprobability1. Theorem1. TheDSFconstructedonthehomogeneousPPPNisa.s.atree. Letusremarkthattheisotropyandthescale-invarianceofthePPPNimplythatTheorem1 stillholdswhenthedirectione x isreplacedwithanygivenu ∈ R 2 andforanygivenvalueof theintensityofN. Theorem1meansthata.s.thepathsintheDSF,withdirectione x andcomingfromanytwo pointsX,Y∈N,eventuallycoalesce.Inotherwords,anytwopointsX,Y∈Nhaveacommon ancestorsomewhereintheDSF.ThiscanbeseenonsimulationsofFigure1. 1