On the Coalescence Time Distribution in Multi-type Supercritical Branching Processes

Dit artikel presenteert een formule voor de verdelingsfunctie van de tijd tot de meest recente gemeenschappelijke voorouder in meervoudige superkritische Galton-Watson-processen, waarbij gebruik wordt gemaakt van de Harris-Sevastyanov-transformatie om harmonische momenten te analyseren en effectieve benaderingen te bieden.

De kern

De Stamboom van een Groeiende Familie: Een Simpele Uitleg van dit Wetenschappelijk Artikel

Stel je voor dat je een gigantische, onzichtbare familie hebt die zich voortplant. Elke generatie krijgen de mensen kinderen, en die kinderen krijgen weer kinderen. Soms stopt een tak van de familie met voortplanten (uitsterven), maar in dit artikel kijken we naar een familie die explosief groeit. Ze worden steeds talrijker, net als een bacteriecultuur in een petrischaal of een virus dat zich verspreidt.

De auteurs van dit artikel, Janique Krasnowska, Paul Jenkins en Adam Johansen, willen een heel specifiek vraagstuk oplossen: Als we nu, na heel veel generaties, een paar willekeurige mensen uit deze enorme familie pakken, hoe ver moeten we terug in de tijd om hun gemeenschappelijke voorouder te vinden?

Hier is hoe ze dat aanpakken, vertaald naar alledaagse taal:

1. Het Grote Probleem: De "Knoop" in de Geschiedenis

Stel je voor dat je een foto maakt van een stad met 10 miljoen mensen (generatie $T$). Je pikt er 5 willekeurige mensen uit. Je vraagt je af: "Wanneer leefden deze 5 mensen hun laatste gezamenlijke voorouder?"

In een kleine, stabiele familie is dat makkelijk te berekenen. Maar in een familie die exponentieel groeit (elke generatie verdubbelt of verdrievoudigt het aantal), wordt het een chaos. De meeste mensen in de huidige generatie zijn niet verwant aan elkaar; ze komen uit heel verschillende takken van de boom. Maar als je ver genoeg terugkijkt, komen die takken samen.

De vraag is: Hoe ver moeten we teruggaan (naar generatie $t$) voordat we die gemeenschappelijke voorouder vinden?

2. De Uitdaging: Het is te groot om te tellen

Het probleem is dat als je terugkijkt naar generatie 1, 2 of 3, er nog maar heel weinig mensen waren. Maar als je naar generatie 100 kijkt, zijn er misschien biljoenen mensen. Het is onmogelijk om elke stamboom van elke persoon te tekenen en te volgen. Het is alsof je probeert elke druppel regen in een orkaan te tellen.

De auteurs zeggen: "Laten we niet proberen de hele boom te tekenen. Laten we kijken naar de statistieken."

3. De Oplossing: Een Magische Spiegel (De Harris-Sevastyanov Transformatie)

Dit is het meest creatieve deel van het artikel. De auteurs gebruiken een wiskundige truc, een soort "magische spiegel", die ze de Harris-Sevastyanov-transformatie noemen.

• De Originele Wereld: In de echte wereld kan de familie uitsterven. Soms stopt een tak helemaal. Dit maakt de wiskunde heel lastig.
• De Gespiegelde Wereld: De auteurs creëren een virtuele, gespiegelde versie van de familie. In deze gespiegelde wereld kan niemand uitsterven. Iedereen heeft altijd nakomelingen.

Waarom doen ze dit? Omdat het berekenen van statistieken in een wereld waar niemand sterft, veel makkelijker is. Het is alsof je in plaats van een rommelige, rommelige kamer (de echte wereld) een perfect opgeruimde kamer bekijkt (de gespiegelde wereld) om te zien hoe de meubels eruitzien.

De auteurs bewijzen dat je de antwoorden voor de echte, rommelige wereld kunt afleiden uit de antwoorden van de opgeruimde, gespiegelde wereld. Ze zeggen eigenlijk: "Als we weten hoe snel de familie groeit in de 'perfecte' wereld, weten we ook hoe snel de 'gemeenschappelijke voorouder' gevonden wordt in de echte wereld."

4. De Resultaten: Grenzen Zetten

In plaats van één exact getal te geven (wat onmogelijk is zonder de hele geschiedenis te kennen), geven ze grenzen.

• De Ondergrens: "We weten zeker dat we niet later dan generatie X hoeven terug te kijken."
• De Bovengrens: "We weten zeker dat we niet eerder dan generatie Y hoeven terug te kijken."

Hoe sneller de familie groeit (hoe "supercritisch" ze zijn), hoe dichter deze twee grenzen bij elkaar komen. Dat betekent: hoe groter de familie, hoe makkelijker het is om te voorspellen waar de gemeenschappelijke voorouder zit.

5. Waarom is dit nuttig? (De Praktijk)

Dit klinkt misschien als pure wiskunde, maar het heeft echte toepassingen:

• Biologie: Het helpt wetenschappers begrijpen hoe virussen of bacteriën zich verspreiden. Als je weet hoe snel een virus "coalesceert" (samenvloeit tot één bron), kun je beter voorspellen waar een epidemie vandaan komt.
• Genetica: Het helpt bij het begrijpen van hoe genen zich door een populatie verspreiden.
• Computers: Omdat het onmogelijk is om echte simulaties te draaien voor enorme populaties (de computer zou ontploffen van de geheugenbehoefte), kunnen onderzoekers nu met deze formules een heel goed schatting maken zonder alles te hoeven simuleren.

Samenvattend

De auteurs hebben een manier bedacht om de "stamboom" van een gigantisch, groeiend gezin te doorgronden zonder elke tak te hoeven tekenen. Ze gebruiken een slimme wiskundige truc (de spiegel) om de moeilijke vragen over uitsterven en groei om te zetten in makkelijke vragen. Hierdoor kunnen we nu veel beter voorspellen hoe ver we terug moeten in de tijd om de oorsprong van een groep mensen (of cellen, of virussen) te vinden.

Het is alsof ze een kaart hebben getekend van een enorme, onbekende stad, niet door elke straat te lopen, maar door te kijken naar de windrichting en de snelheid van de rivier die erdoorheen stroomt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "On the Coalescence Time Distribution in Multi-type Supercritical Branching Processes" in het Nederlands.

Titel: De Coalescentie-tijdverdeling in multi-type superkritische vertakkingsprocessen

Auteurs: Janique Krasnowska, Paul A. Jenkins, Adam M. Johansen (Universiteit van Warwick)

---

1. Probleemstelling

Het artikel onderzoekt de genealogie van een populatie die evolueert volgens een discrete-tijd, multi-type, superkritische Galton-Watson-vertakkingsprocess.

• Context: In de evolutiebiologie en genetica is het begrijpen van de voorouders van een steekproef van individuen (terug in de tijd) cruciaal. Dit wordt vaak gemodelleerd via coalescentieprocessen.
• Uitdaging: Bestaande theorieën zijn voornamelijk beperkt tot single-type processen of kritische multi-type processen. Voor superkritische multi-type processen (waar de populatie exponentieel groeit of uitsterft) ontbreekt een algemene formule voor de verdeling van de tijd tot de Meest Recente Gemeenschappelijke Voorouder (MRCA) van een steekproef, vooral wanneer het aantal typen oneindig kan zijn en uitsterven mogelijk is.
• Specifiek doel: Het afleiden van een formule voor de verdelingsfunctie van de generatie $t$ waarin de MRCA van $k$ willekeurig gekozen individuen uit generatie $T$ voorkomt, in de limiet $T \to \infty$.

2. Methodologie

De auteurs combineren kansrekening, asymptotische analyse en transformatietechnieken om het probleem aan te pakken:

• Modelopbouw:

  • Een multi-type Galton-Watson proces $Z_t$ met een type-ruimte $S$ (eindig of aftelbaar oneindig).
  • De populatie is superkritisch (de verwachte nakomelingen per individu is > 1), wat leidt tot exponentiële groei of uitsterven.
  • Er wordt gebruik gemaakt van de Perron-Frobenius-theorie voor de gemiddelde nakomelingenmatrix $M$ om de groeifactor ($R$) en de invariante vectoren ($u, \nu$) te definiëren.

• Asymptotische Analyse:

  • Het proces wordt genormaliseerd met $R^{-t}$. Volgens de stelling van Kesten-Stigum convergeert deze genormaliseerde populatiegrootte naar een willekeurige variabele $W$ (de limietverdeling).
  • De auteurs gebruiken de Decompositie-eigenschap van vertakkingsprocessen: de populatie op tijdstip $T$ kan worden gezien als een som van onafhankelijke sub-processen die starten bij individuen op tijdstip $t$.

• Harris-Sevastyanov Transformatie:

  • Een van de grootste technische uitdagingen is het berekenen van harmonische momenten (verwachte waarden van $1/|Z_t|^r$) van de populatiegrootte, aangezien deze lastig te berekenen zijn voor grote$t$.
  • De auteurs generaliseren de Harris-Sevastyanov-transformatie naar multi-type processen. Deze transformatie converteert het oorspronkelijke proces (dat kan uitsterven) naar een nieuw proces $Y_t$ dat nooit uitsterft (uitstervingskans = 0).
  • Hierdoor kunnen momenten van het originele proces (voorwaarde op niet-uitsterven) worden begrensd door momenten van het getransformeerde proces op generatie 1, wat numeriek veel eenvoudiger is.

• Numerieke Benadering:

  • Voor de praktische toepassing wordt een methode ontwikkeld om de verdeling van de limietvariabele $W$ te benaderen via inverse discrete Fourier-transformatie van de karakteristieke functie, die op zijn beurt wordt benaderd via Taylor-polynomen van de genererende functies.

3. Belangrijkste Bijdragen en Resultaten

Het artikel presenteert drie centrale stellingen en een corollarium:

• Stelling 3 (De Coalescentie-verdeling):

  • De auteurs leiden een exacte formule af voor de limiet van de kans dat de MRCA van $k$ individuen (gekozen uit generatie $T$) ouder is dan $t$, gegeven dat de populatie niet is uitgestorven.
  • De formule wordt uitgedrukt in termen van de limietvariabele $W$ van de genormaliseerde populatiegrootte:
    $$\lim_{T \to \infty} P(X_{T,k} < t \mid |Z_T| \ge k) = 1 - E\left[ \frac{\sum (W_{t,s}^{(i)})^k}{(\sum W_{t,s}^{(i)})^k} \mid |Z_\infty| > 0 \right]$$
  • Dit generaliseert eerdere resultaten (zoals die van [21]) naar processen met uitstervingskans en een oneindig aantal typen.

• Stelling 4 (Grenzen via Harmonische Momenten):

  • Omdat de exacte berekening van Stelling 3 moeilijk is voor grote $t$, worden boven- en ondergrenzen afgeleid voor de coalescentiekans.
  • Deze grenzen hangen af van de harmonische momenten van de totale populatiegrootte $|Z_t|$ (bijv. $E[1/|Z_t|]$).
  • De auteurs tonen aan dat de coalescentiekans exponentieel convergeert naar 1 naarmate $t$ toeneemt.

• Stelling 5 (Relatie met Getransformeerde Proces):

  • Om de harmonische momenten van $|Z_t|$ praktisch berekenbaar te maken, worden deze begrensd door momenten van het Harris-Sevastyanov getransformeerde proces $Y_1$ (op generatie 1).
  • Dit elimineert de noodzaak om iteraties van genererende functies te berekenen voor grote $t$. De complexiteit wordt teruggebracht tot het berekenen van momenten op generatie 1.

• Corollarium 1 (Expliciete Exponentiële Convergentie):

  • Door Stelling 4 en 5 te combineren, krijgen de auteurs expliciete boven- en ondergrenzen die tonen dat de coalescentiekans exponentieel snel naar 1 convergeert, met een snelheid die bepaald wordt door de eigenschappen van het getransformeerde proces $Y_1$.

4. Numerieke Resultaten

De auteurs valideren hun theorie met numerieke simulaties in Python en Julia:

• Systeem: Ze testen zowel een licht superkritisch systeem als een sterk superkritisch systeem (met verschillende Poisson-verdelingen voor nakomelingen).
• Vergelijking: De geschatte coalescentiekans (via hun formule en Monte Carlo-sampling van $W$) wordt vergeleken met directe simulatie van de genealogie.
• Resultaat: De geschatte waarden komen zeer goed overeen met de directe simulatie.
• Efficiëntie: Voor sterk superkritische systemen (waar de populatiegrootte exponentieel groeit tot $10^9$ of meer) is directe simulatie computatief onmogelijk vanwege geheugenbeperkingen. De methode van de auteurs (gebaseerd op Stelling 3 en 5) is echter vele malen sneller (seconden versus uren/dagen) en blijft nauwkeurig.

5. Betekenis en Impact

• Theoretische Uitbreiding: Het artikel vult een belangrijke lacune in de theorie van vertakkingsprocessen door de genealogie van superkritische multi-type processen (met uitsterven en oneindige typen) wiskundig te karakteriseren.
• Praktische Toepasbaarheid: De afgeleide formules en grenzen bieden een efficiënt alternatief voor brute-force simulatie. Dit is cruciaal voor toepassingen in:
  • Epidemiologie: Het begrijpen van de oorsprong van infectieclusters in groeiende populaties.
  • Evolutiebiologie: Het reconstrueren van stambomen van cellen of genen in groeiende weefsels.
  • Genetica: Het analyseren van selectie en drift in populaties die niet in evenwicht zijn.
• Rekenkracht: De generalisatie van de Harris-Sevastyanov-transformatie maakt het mogelijk om complexe momenten te benaderen die anders onberekenbaar zouden zijn, wat de weg vrijmaakt voor verdere analyse van genealogische structuren in complexe systemen.

Kortom, dit werk biedt zowel een diepgaande theoretische basis als een praktische, computerefficiënte methode om de coalescentie-tijd in groeiende, heterogene populaties te analyseren.