Rotating random trees with Skorokhod's $M_1$ topology

Deze studie breidt de codering van gemeten $\mathbb{R}$-bomen uit naar càdlàg-functies via Skorokhod's $M_1$-topologie en toont aan dat de rotatie van kritieke bomen met een verdeling in het domein van aantrekkingskracht van een $\alpha$-stabiele wet ($\alpha \in (1,2)$) leidt tot een schaal-limiet die verschilt van het Gaussische geval en overeenkomt met de bomen gecodeerd door $\alpha$-stabiele Lévy-processen.

De kern

Hier is een uitleg van het onderzoek van Antoine Aurillard, vertaald naar een begrijpelijk verhaal met creatieve metaforen.

De Grote Boom-Transformatie: Van Struik tot Boom

Stel je voor dat je een enorme verzameling bomen hebt. Niet zomaar bomen, maar wiskundige bomen die groeien op een heel specifieke manier: Bienaymé-bomen. Deze bomen groeien volgens een kansspel waarbij elke tak een bepaald aantal nieuwe takjes kan krijgen.

De auteur van dit paper, Antoine Aurillard, onderzoekt wat er gebeurt als je deze bomen ondergaat aan een speciale operatie: Rotatie.

1. De Rotatie: Een Wiskundige Dans

Stel je een gewone boom voor met een stam en takken die naar links en rechts uitsteken. De "rotatie" is een wiskundige truc die deze boom omvormt tot een binomiale boom (een boom waar elke tak precies twee kinderen kan hebben, of geen enkele).

Het is alsof je een oude, rommelige boom in je tuin neemt en hem herschikt tot een perfect symmetrisch, gestructureerd struikgewas.

• De oude regel: Als je een boom rotatieert, verandert de vorm volledig.
• De vraag: Als je deze rotatie toepast op een enorme boom (met duizenden takken), ziet de nieuwe boom er dan nog steeds uit als een gewone boom, of verandert hij fundamenteel van aard?

2. Het Nieuwe Gereedschap: De "M1-Topologie"

Om deze enorme bomen te bestuderen, gebruiken wiskundigen vaak een "kaart" om de boom te tekenen. Normaal gesproken tekenen ze deze kaart als een gladde, continue lijn (zoals een heuvelachtig landschap).

Maar Aurillard ontdekt dat voor bepaalde soorten bomen (die groeien met "explosieve" sprongen), deze gladde kaart niet werkt. De lijn is dan niet glad, maar heeft stapjes (zoals een trap of een digitale grafiek).

Om deze "stap-achtige" bomen te kunnen bestuderen, gebruikt hij een nieuw soort meetlat: de Skorokhod M1-topologie.

• De Metafoor: Stel je voor dat je twee lijnen vergelijkt.
  • De oude meetlat (J1) zegt: "Deze lijnen zijn verschillend omdat de ene een sprong maakt op tijdstip X en de andere op tijdstip Y."
  • De nieuwe meetlat (M1) zegt: "Het maakt niet uit wanneer de sprong gebeurt, zolang de vorm van de sprong maar hetzelfde is. Laten we de tijd even rekken of samendrukken om ze op elkaar te laten lijken."
    Dit stelt Aurillard in staat om bomen te vergelijken die op het eerste gezicht heel anders lijken, maar in feite dezelfde "geest" hebben.

3. De Twee Werelden: Normaal vs. Exotisch

Het paper maakt een cruciaal onderscheid tussen twee soorten bomen, afhankelijk van hoe ze groeien:

A. De "Normale" Bomen (Gaussisch geval, $\alpha = 2$)
Stel je voor dat de takjes groeien volgens een normaal verdeling (zoals de grootte van mensen in een stad).

• Het resultaat: Als je een enorme boom rotatieert, verandert hij van vorm, maar hij blijft fundamenteel hetzelfde. Het is alsof je een foto van een boom vergroot of verkleint.
• De conclusie: De rotatie werkt als een vergrootglas. De structuur blijft een "Brownse Boom" (een wiskundig bekend type boom), alleen is hij iets groter of kleiner.

B. De "Exotische" Bomen (Stabiele geval, $1 < \alpha < 2$)
Stel je voor dat de bomen groeien met enorme, onvoorspelbare sprongen (zoals een beurscrash of een aardbeving). Hier kunnen er ineens heel veel takken tegelijk ontstaan.

• Het resultaat: Als je een enorme boom van dit type rotatieert, gebeurt er iets magisch. De boom verandert niet alleen van grootte, maar verandert van soort.
• De nieuwe vorm: De gerotatereerde boom wordt een $T_x(\alpha)$ boom. Dit is een heel nieuw type wiskundig object. Het is een boom die "binaire" is (altijd 2 kinderen), maar die ook een heel andere geometrie heeft.
  • Interessant detail: De oude boom had soms takken met oneindig veel kinderen. De nieuwe boom heeft dit niet; hij is strakker en heeft een andere "ruimtelijke dimensie".

4. De Link met "Loop-Struiken"

Aurillard ontdekt ook een verbinding met iets dat "Loop-Struiken" (Looptrees) worden genoemd.

• De Metafoor: Stel je voor dat je de takken van een boom niet als lijnen tekent, maar als een reeks aaneengesloten cirkels (zoals een ketting of een slinger).
• De gerotatereerde boom ($T_x$) blijkt een soort "skelet" te zijn dat precies past in deze ketting van cirkels. Het is alsof je een boom neemt en hem omvormt tot het frame van een fiets, terwijl de oorspronkelijke boom de wielen waren.

5. De Spiegelbeeld-Transformatie (Co-rotatie)

Aurillard onderzoekt ook een tegenhanger van de rotatie, de "co-rotatie".

• Bij de normale rotatie verandert de boom van vorm (van glad naar gestapeld).
• Bij de co-rotatie blijft de "code" van de boom (de Łukasiewicz-wandeling) bijna hetzelfde, zelfs als de boom er anders uitziet.
• De les: Twee bomen kunnen er heel verschillend uitzien (zoals een boom en een struik), maar hun onderliggende "DNA" (de wandeling) kan identiek zijn. Of andersom: twee bomen kunnen hetzelfde DNA hebben, maar door een rotatie totaal verschillende vormen aannemen.

Samenvatting in één zin

Antoine Aurillard laat zien dat als je een wiskundige boom "rotatieert" (herstructureert), hij bij normale bomen alleen maar groter of kleiner wordt, maar bij exotische, explosief groeiende bomen verandert hij in een compleet nieuw type boom met een eigen unieke geometrie, en hij heeft hiervoor een nieuwe meetlat ontwikkeld om deze sprongachtige veranderingen te kunnen volgen.

Waarom is dit belangrijk?
Het helpt ons te begrijpen hoe complexe systemen (zoals netwerken, stromen of zelfs genetische structuren) reageren op grote veranderingen. Soms blijft het systeem stabiel, en soms transformeert het volledig in iets nieuws.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Rotating random trees with Skorokhod's M1 topology" van Antoine Aurillard, geschreven in het Nederlands.

Titel: Rotatie van willekeurige bomen met de M1-topologie van Skorokhod

1. Probleemstelling en Context

Het artikel richt zich op de schaallimieten (scaling limits) van grote, kritieke Bienaymé-Galton-Watson (BGW) bomen, specifiek onderworpen aan een bekende bijectie tussen vlakke bomen en binaire bomen, de zogenaamde rotatie (aangeduid als $Rot$).

• Achtergrond: In de studie van willekeurige bomen worden bomen vaak gecodeerd door continue functies (zoals het contourproces, het hoogteproces of de Łukasiewicz-wandeling). De convergentie van deze processen impliceert convergentie van de bomen zelf onder de Gromov-Hausdorff-Prokhorov (GHP) topologie.
• Het probleem: Bestaande resultaten (zoals die van Marckert voor uniforme bomen) tonen aan dat rotatie op grote schaal werkt als een dilatatie (vergroting) van de afstanden. Echter, voor kritieke BGW-bomen met een nakomelingenverdeling die in het domein van aantrekking valt van een stabiele verdeling met index $\alpha \in (1, 2]$, is het gedrag minder duidelijk.
• De uitdaging: Wanneer $\alpha < 2$, hebben de coderende processen van de geroteerde bomen discontinuïteiten (sprongen). De gebruikelijke topologieën voor willekeurige bomen (uniforme topologie of Skorokhod's $J1$-topologie) zijn onvoldoende om de convergentie van deze discontinu processen naar een limiet te beschrijven, omdat de spronggrootte en -plaatsen niet perfect overeenkomen. Er is een zwakkere topologie nodig die convergentie toestaat ondanks ongesynchroniseerde sprongen.

2. Methodologie

De auteur introduceert een veralgemening van de codering van $\mathbb{R}$-bomen om discontinuïteiten te hanteren, en gebruikt combinatorische relaties om de limieten te analyseren.

• Parametrische representaties en M1-topologie:

  • De kern van de methode is het gebruik van parametrische representaties van càdlàg-functies (rechtscontinu met links-limieten), een concept dat fundamenteel is voor de Skorokhod $M1$-topologie.
  • In plaats van de grafiek van een functie direct te gebruiken, wordt de grafiek "opgevuld" met verticale segmenten op de plaatsen van discontinuïteit. Een parametrische representatie is een continue, niet-dalende parametrisering van deze uitgebreide grafiek.
  • Dit maakt het mogelijk om een $\mathbb{R}$-boom $T_x$ te definiëren die gecodeerd is door een discontinu excursionsproces $x$, waarbij de continuïteit van de afbeelding $x \mapsto T_x$ behouden blijft onder de $M1$-topologie.

• Combinatorische Analyse van Rotatie:

  • De rotatie $Rot$ wordt geanalyseerd via een geometrische constructie en een recursieve definitie.
  • Een cruciale stap is het introduceren van de interne boom $(Rot\, T)^\circ$, die bestaat uit de interne knopen van de geroteerde boom.
  • De auteur gebruikt de spiegeltransformatie (mirror transformation, $T \mapsto T^\div$) om een relatie te leggen tussen de Łukasiewicz-wandeling van de originele boom $T_n$ en de hoogtes van de knopen in de geroteerde boom.
  • Er worden combinatorische relaties afgeleid tussen het contourproces van de geroteerde boom en de coderende processen van de originele boom (via de gespiegelde versie).

• Convergentie-analyse:

  • De bewijzen maken gebruik van de continuïteit van de codering onder de $M1$-topologie (Propositie 1.1 en 1.2).
  • Het bewijs van de gezamenlijke convergentie van de coderende processen ($s_{T_n}, c_{T_n}, s_{Rot\, T_n}, c_{Rot\, T_n}$) wordt opgebouwd door de processen te vergelijken via combinatorische lemmata die de $M1$-afstand tussen ze schalen.

3. Belangrijkste Resultaten

Het paper levert drie hoofdcategorieën van resultaten:

A. Theorie van $\mathbb{R}$-bomen met càdlàg-codering

• Definitie: Er wordt een unieke $\mathbb{R}$-boom $T_x$ en een maat $\mu_x$ gedefinieerd voor elke càdlàg-excursie $x \in D_0([0,1], \mathbb{R}^+)$.
• Continuïteit: De afbeelding $x \mapsto (T_x, \mu_x)$ is continu met betrekking tot de $M1$-topologie op functieruimten en de Gromov-Hausdorff-Prokhorov ($d_{GHP}$) topologie op gemeten bomen.
• Eigenschappen van de limietboom: Voor een $\alpha$-stabiele Lévy-excursie ($\alpha \in (1, 2)$) is de resulterende boom $T_x$:
  • Binair: Alle knopen hebben graad 1, 2 of 3.
  • Leaves: De verzameling bladeren is dicht in de boom.
  • Dimensie: De Hausdorff-dimensie is $\alpha$ (in tegenstelling tot de stabiele boom $T_h$ die dimensie $\alpha/(\alpha-1)$ heeft).
  • Relatie met Looptrees: $T_x$ kan worden gezien als een "spanning tree" van de stabiele looptree $L_x$ (geïntroduceerd door Curien & Kortchemski).

B. Schaallimieten van Geroteerde Bomen (Theorema 1.3)
Het gedrag van de geroteerde boom $Rot\, T_n$ hangt fundamenteel af van de index $\alpha$:

• Gaussisch geval ($\alpha = 2$, eindige variantie $\sigma^2$):
  De rotatie werkt als een dilatatie. De schaallimiet van de geroteerde boom is hetzelfde als die van de originele boom (een Brownse CRT), maar met afstanden vermenigvuldigd met een constante factor $(1 + \sigma^2/2)$.
  $$\left(\frac{1}{\sqrt{n}}T_n, \frac{1}{\sqrt{n}}Rot\, T_n\right) \xrightarrow{d} \left(\frac{2}{\sigma}T_e, \frac{2+\sigma^2}{\sigma}T_e\right)$$
• Stabiel geval ($\alpha \in (1, 2)$, oneindige variantie):
  De rotatie verandert de geometrie van de boom. De schaallimiet is geen stabiele boom meer, maar een nieuwe familie van bomen $T_x$ gecodeerd door de càdlàg-excursie van een spectraal positieve $\alpha$-stabiele Lévy-proces.
  $$\left(\frac{\ell(n)}{n^{1-1/\alpha}}T_n, \frac{1}{\ell(n)n^{1/\alpha}}Rot\, T_n\right) \xrightarrow{d} (T_h, T_x)$$
  Hierbij is $T_h$ de stabiele boom en $T_x$ de nieuwe limiet. De schalingsfactoren zijn verschillend, en de limietbomen zijn niet isometrisch.

C. Co-rotatie en Łukasiewicz-wandelingen

• De auteur introduceert een symmetrische tegenhanger, de co-rotatie ($Tor$).
• Een opmerkelijk resultaat is dat de Łukasiewicz-wandeling van $Tor\, T_n$ asymptotisch identiek is aan die van $T_n$ (zelfs als de bomen zelf verschillende schaallimieten hebben).
• Dit illustreert dat de Łukasiewicz-wandeling niet altijd de volledige geometrische structuur van de schaallimiet vastlegt, en dat de $M1$-topologie essentieel is om deze subtiliteiten te onderscheiden.

4. Significantie en Bijdrage

• Methodologische doorbraak: Het artikel toont aan dat de $M1$-topologie van Skorokhod een krachtig hulpmiddel is voor de studie van willekeurige bomen met zware staarten ($\alpha < 2$), waar de gebruikelijke $J1$-topologie faalt vanwege de mismatch in spronggrootte.
• Nieuwe willekeurige objecten: Het identificeert en karakteriseert een nieuwe klasse van $\mathbb{R}$-bomen ($T_x$) die ontstaan als schaallimiet van geroteerde bomen. Deze bomen hebben unieke eigenschappen (zoals binaire structuur en specifieke Hausdorff-dimensie) die ze onderscheiden van de bekende stabiele bomen.
• Verbinding tussen structuren: Het legt een diepgaande link tussen de combinatoriek van boomrotaties, de theorie van stabiele processen, en de meetkunde van looptrees.
• Verrijking van de theorie: Het werk breidt de klassieke resultaten van Aldous en Duquesne uit naar een breder spectrum van kritieke verdelingen en toont aan dat operaties zoals rotatie fundamenteel verschillende effecten kunnen hebben afhankelijk van de onderliggende verdeling (eindige vs. oneindige variantie).

Kortom, dit paper biedt een rigoureuze wiskundige onderbouwing voor het gedrag van geroteerde willekeurige bomen en opent de deur tot het bestuderen van andere operaties op bomen die leiden tot discontinuïteiten in de coderende processen.