Abstrakt. Betrakta en Markov kedja på utrymmet av rotade riktiga binära träd som slumpmässigt tar bort blad och återinför dem på en slumpmässig kant och lämpligt skalar om längden på kanterna. Denna kedja introducerades av David Aldous som antog en spridningsgräns för denna kedja, allteftersom storleken på trädet växer, på utrymmet för kontinuumträd. Vi bevisar existensen av en process på continuum träd, som genom en slumpmässig tid förändring, visar egenskaper som man skulle förvänta sig av den förmodade Aldous diffusion. Förekomsten av vår process bevisas genom att överväga en explicit skalad gräns för en Poissonized version av Aldous Markov kedjan som körs på ändliga träd. Analysen innebär att ta gränsen för en sekvens av att dela träd vars åldersprocesser konvergerar men konturprocessen inte gör det. Flera formler om begränsningsprocessen härleds.  En Cladogram är ett orotat halvmärkt binärt träd. Det vill säga, varje vertex som inte är av grad man måste ha grad tre. De hörn av grad en kallas blad som är märkta med {1, 2,.., n}, medan varje annan vertex kommer att kallas inre hörn. Därav följer att om ett sådant träd har exakt n blad, måste det ha 2n − 3 kanter. I [4, 5] tar Aldous hänsyn till följande Markovkedja på utrymmet för n-leaf Cladograms. För en exakt beskrivning definierar vi först två operationer på Cladograms noggrant följa [5], som vi hänvisar läsarna för mer detaljer. (i) Att ta bort ett blad i. Bladen i är fästa vid en kant e 1 till en grenpunkt b där två andra kanter e 2 och e 3 är infallande. Se figur 1. Ta bort kant e 1 och grenpunkt b, och sedan slå ihop de två återstående kanterna e 2 och e 3 till en enda kant e. Det resulterande trädet har 2n - 5 kanter. (ii) Att lägga ett blad till en kant f. Skapa en grenpunkt b som delar kanten f i två kanter f 2, f 3 och fästa bladet i till grenpunkt b via en ny kant f 1. Detta återställer antalet blad och kanter till trädet. Låt τ n betecknar den finita samlingen av alla n-blad Cladograms. Låt T, T vara element på τ n. Skriv T. T om T = T och T kan erhållas från T genom att följa de två åtgärderna ovan för något val av i och f. Således en τ n värderad kedja kan beskrivas genom att säga: ta bort blad jag jämnt på slumpmässigt, sedan plocka kant f på slumpmässiga och re-attach i till f. I synnerhet dess övergångsmatris är Detta leder till en symmetrisk, aperiodisk, och irreducible finita tillstånd utrymme Markov kedja. Schweinsberg [27] visade att avkopplingstiden för denna kedja är O(n 2 ), förbättra ett tidigare resultat i [5]. Vi kommer att hänvisa till denna Markovkedja som den Aldous Markov-kedjan i följande text. Problemet av intresse för oss i denna artikel är att etablera en begränsande diffusion för denna sekvens av Markov kedjor som n tenderar till oändlighet. Det är inte helt rigoröst i detta skede vad vi menar med en gräns här. Vad är till exempel vårt begränsade tillståndsutrymme? Närmare svar på sådana frågor kommer att ges senare. Grovt kommer vårt tillstånd utrymme att vara utrymmet för continuum träd, dvs kompakta metriska utrymmen utan slingor som stöder en sannolikhetsmått på dem. Därför letar vi efter en kontinuerlig Markovprocess på utrymmet för continuum träd som kan argumenteras som en svag gräns för ovanstående sekvens av kedjor. Det finns några tekniska problem med att arbeta med en orotad Cladogram. Därför kommer vi att göra en liten förändring i ovanstående modell och överväga Cladograms där en framstående vertex i trädet vid tiden noll markeras som rot som aldrig tas bort och fortsätter som roten av alla efterföljande träd. I stället för att kalla Cladograms kommer vi helt enkelt att kalla sådana träd som rotade binära träd. Se Avsnitt 2 för att hitta formella definitioner av vilken typ av träd vi arbetar med. När träd är rotade, är det naturligt att associera en familj struktur med det där roten är en förfader, och varje vertex ger upphov till ett antal barn / avkomma. Vi kommer ofta att använda denna analogi vars innebörd kommer att vara uppenbar ur sammanhanget. 1.1. De åtgärder som föreskrivs i denna förordning är förenliga med yttrandet från ständiga kommittén för växter, djur, livsmedel och foder. Poissonisering. Vi introducerar nu det viktiga begreppet Poissonization av Markovkedjan som beskrivs ovan. En utmanande aspekt av Aldous Markov-kedjan på Cladograms är att antalet blad förblir detsamma vid varje steg i kedjan. Saker och ting blir enklare om vi antar Poissonized version av Markov kedjan: varje blad har en exponentiell klocka med hastighet 2 fäst vid det som bestämmer tidpunkten för deras avlägsnande (dödar). Varje kant har också en exponentiell klocka av klass 1 vid vilken punkt ett nytt par hörn (en inre punkt och ett blad ansluten med en kant) introduceras på den kanten. Antalet födslar och dödsfall väljs för att tillgodose det faktum att det finns ungefär dubbelt så många kanter som blad. Vi kommer att hänvisa till denna modell som den Poissonized Aldous Markov kedjan. Denna Poissonization ändrar Markov kedjan när antalet blad är ändliga. Det finns dock starka skäl att tro att den begränsande diffusionen för den icke-poissoniserade kedjan är lika i lag den begränsande spridningen av den Poissoniserade kedjan via en stokastisk tidsförändring. Vi anför ett argument nedan för att framföra vårt argument. Går tillbaka till Aldous Markov kedjan (orotad), överväga en gren punkt b i trädet T. Det delar insamlingen av blad naturligt i tre uppsättningar. Låt X(T) = (X 1, X 2, X 3 )(T) betecknar vektorn av andelen blad i varje uppsättning. Det kan verifieras (se Pal [23]) att Markov kedjan på Cladograms inducerar en Markov kedja på dessa vektor av proportioner, som, när den körs med n 2 / 2 hastighet, konvergerar i lag till en spridning på tillståndsutrymmet {(x 1, x 2, x 3 ), x i ≥ 0, x 1 + x 2 + x 3 = 1}. Lagen av denna diffusion kallas Negative-Wright-Fisher eller NWF (1/2, 1/2, 1/2). I Pal [23] visas det att NWF-lagen kan erhållas genom att man tar hänsyn till förhållandet mellan kvadratbesselprocesser med negativa dimensioner. En omfattande behandling av BESQ-processer finns i boken av Revuz & Yor [26]. Denna familj av endimensionella diffusioner indexeras av en enda verklig parameter (kallas dimension) och är lösningar av de stokastiska differentialekvationer där β är en endimensionell standard Brownian rörelse. Vi betecknar lagen i denna process med Q  på x. Det kan visas att ovanstående SDE medger en unik stark lösning tills den träffar ursprunget. Den klassiska modellen medger bara paramater  på 4 SOUMIK PAL vara icke-negativa. En förlängning, som infördes av Göing-Jaeschke & Yor [15], gör att parametern är negativ. Det är väl känt att BESQ-processen med en icke-negativ dimension är diffusionsgränsen, eftersom antalet initiala partiklar går till oändligheten, för en kritisk (diskret eller kontinuerlig tid) Galton-Watson träd med en hastighet av invandring  på. Till exempel, Detta händer för en kontinuerlig tid, binära Galton-Watson, varje individ dör eller reproducerar i takt 2 och det finns en tillströmning av nya medlemmar i takt. Det framgår av samma bevis för att invandringen, när den är negativ, förändras till emigration, dvs. i takt med att medlemmarna lämnar familjen tills det inte finns någon som överlever. Följande konstruktion av NWF-processer återfinns i [23, Theorem 8]. Det här är Lemma 1. Låt Z = (Z 1, Z 2, Z 3 ) vara en vektor av 3 iid BESQ processer dimension −1. Låta vara summan Sedan finns det en N W F (1/2, 1/2, 1/2) process (μ 1, μ 2, μ 3 ) för vilken följande jämlikhet innehar: En mycket liknande resultat håller när i stället för att överväga en gren punkt vi anser flera gren punkter och titta in i uppdelningen av bladmassor som genereras av dessa gren punkter. Vektorn för proportioner medger en spridningsgräns som kan erhållas genom en slumpmässig tidsförändring från oberoende BESQ-processer (av möjligen både positiva och negativa dimensioner). Därför är det naturligt att söka efter en Markov kedja på Cladograms sådan att bladmassor i partitioner som genereras av grenpunkter konvergera till BESQ-processer. Detta är exakt vad som händer för Poissonized Markov kedja eftersom antalet blad i varje partition utvecklas som en oberoende Galton-Watson förgrening process med invandring eller utvandring. Därför ger Theorem 1 oss den viktiga ledtråden till idén om poissonisering av Aldous kedja och det korrekta värdet av utvandringstakten som är avgörande i följande. Fler exempel på Poissonization finns i Markov kedjor som Wright-Fisher kedjan vars Poissonized version är en grenningsprocess med invandring. Spridningsgränsen för den förra är Wright-Fisher-spridningen och spridningsgränsen för den senare är BESQ-processen. Tidsförskjutningsförhållandet mellan de två finns i Pal [22]. Mer påminner om Fleming-Viot-modellen där Superprocessen är den Poissoniserade versionen, och den sats som gör det möjligt för oss att få Fleming-Viot från Superprocessen med en tid och massförändring kallas Perkins Disintegrationsteorem (se Etheridge [11]). Vi avslutar diskussionen med en uppenbar lemma. - Vad är det? - Lemma 2. Betrakta en inre vertex på en ändlig träd som Poissonized Aldous kedja är igång. Denna inre vertex delar bladen av trädet i tre subträd rotade vid vertex. En av dem innehåller den ursprungliga roten. Tänk på antalet blad i någon av de två andra delarna. Processen av det totala antalet blad i dessa underträd följer oberoende kontinuerlig tid binär Galton-Watson förgrening process med en födelse-och dödsfrekvens på två och en emigrationsfrekvens 1 tills en av dem når noll. För fordon av kategorierna M1 och N1 ska följande villkor vara uppfyllda: Kodning av ett träd 1.2. Koda träd efter ålder. Ett grundläggande begrepp som står i centrum för vårt resonemang är den så kallade tidsåldern för ett slumpmässigt träd. Tänk på alla modeller för att generera ett slumpmässigt träd som börjar med en individ. Om efter en enhet av tid senare trädet överlever, då ålder trädet är en. Detta är särskilt användbart när vi har en tid-axel och flera träd börjar gro vid olika tidpunkter. Vid varje givet tillfälle tänker vi på hur många träd som överlevde vid den tiden. Deras tidsåldrar ges av de varaktigheter som de har spirat upp. I denna dynamiska situation egenskaper träd kan beskrivas med sin ålder. Anta till exempel att den totala befintliga populationen i ett dynamiskt växande slumpmässigt träd ges av en kontinuerlig tid Galton-Watson förgrening process. Sedan, med tanke på dess ålder, kan man härleda dess storlek från den villkorliga fördelningen av Galton-Watson grenning process konditionerad för att överleva upp till tid a. Nu kan man faktiskt koda ett helt träd efter tidsåldrarna av dess olika underträd. Vi kommer att diskutera dessa idéer mycket mer i detalj senare i texten. För att ge en uppfattning om vår strategi ger vi dock en förenklad informell beskrivning nedan. Tänk på bilden av ett ändligt träd i figur 2. Variablerna {d 1,. ., d 7 } kommer att betraktas (positiva) avstånd och variablerna {q 1,. ., q 7 } kommer att betraktas som (icke-negativa) massor. Nu konstruerar vi en stokastisk process (A 1, A 2, A 3 ) enligt följande: A 1 tar tre värden d 1 < d 2 < d 7 med sannolikheter proportionella mot q 1, q 2, och q 7 respektive. Med tanke på A 1 bestäms värdet av A 2. Case (i) Antag A 1 = d 1, vi föreställer oss vår process går in i det första underträdet som är märkt med streck. Därefter tar X 2 två värden d 3 < d 5 med sannolikhet proportionell mot q 3 respektive q 6. Case (ii) Antag A 1 = d 2, Sedan vår process går in i den streckade delträdet, och A 2 är d 6 med sannolikhet en, oavsett q 6. Case (iii) Antag A 1 = d 7, sedan A 2 = 0 med sannolikhet en. Läsaren kan nu gissa fördelningen av A 3, Med tanke på värdena i A 1, A 2. I själva verket A 3 = d 4 med sannolikhet en om {A 1 = d 1, A 2 = d 3 }, eller noll annars.
Vi hänvisar till en enda gren med en atomär åtgärd som en sträng av pärlor, se även REF för relaterade strukturer.
On the Aldous diffusion on Continuum Trees. I
{'venue': None, 'journal': 'arXiv: Probability', 'mag_field_of_study': ['Mathematics']}