Kingmans Koaleszenz

Kingmans Koaleszenz ist ein stochastischer Prozess aus der Koaleszenztheorie, einer Theorie, die sich mit stochastischen Prozessen von Partikeln beschäftigt, die mit der Zeit Cluster formen. Solche Prozesse finden Anwendung in der Populationsgenetik, wobei man die Cluster wieder als Partikel interpretiert. Kingmans Koaleszenz hat die besondere Eigenschaft, dass sie in einer Partition von unendlich vielen Partikeln beginnt, sich aber nach jeder positiven Zeit fast sicher endlich viele Cluster formen. Eine Art Big Bang der Stochastik.

Kingmans $n$-Koaleszenz ist der einfachste nicht-triviale stochastische Prozess, um die stochastische Populationsgenetik zu modellieren. Sie lässt sich als Ahnen-Prozess interpretieren, wobei man in der jüngsten Generation beginnt. Es ist ein Markov-Prozess auf einer Population der Größe $n$, so dass sich jeweils zwei Ahnen mit der Rate $1$ verbinden.

Der Prozess ist nach dem britischen Mathematiker John Kingman benannt.

Kingmans n-Koaleszenz

Stochastische Partition

Eine zufällige Partition $\pi$ auf $\mathbb {N}$ ist eine zufällige Äquivalenzrelation auf $\mathbb {N}$. Mit $|\pi |$ bezeichnen wir die Anzahl Äquivalenzklassen, anschaulich bilden diese Blöcke.

Sei ${\mathcal {P}}$ die Menge der zufälligen Partitionen von $\mathbb {N}$, mit ${\mathcal {P}}_{n}$ bezeichnen wir die Untermenge der $[n]$-Partitionen. Wobei $[n]:=\{1,2,\dots ,n\}$ bedeutet.

Mit $\pi '\prec \pi$ bezeichnen wir, dass $\pi '$ durch Verschmelzen zweier Äquivalenzklassen aus $\pi$ entstanden ist, das heißt, es gilt $\pi \subset \pi '$ und $|\pi |=|\pi '|+1$.

Kingmans n-Koaleszenz

Wir definieren einen stochastischen Prozess $(\Pi _{t}^{n})_{t\geq 0}$ auf dem Raum ${\mathcal {P}}_{n}$ mit folgenden Eigenschaften:

1. $\Pi _{0}^{n}$ ist die triviale Partition in Singletons.
2. $\Pi _{t}^{n}$ ist ein starker Markov-Prozess mit Übergangsraten

$q_{\pi ,\pi '}=\lim \limits _{h\downarrow 0}{\frac {\mathbb {P} \left(\Pi _{t+h}=\pi '|\Pi _{t}=\pi \right)}{h}}={\begin{cases}1&\pi '\prec \pi \\0&{\text{sonst}}\end{cases}}$

Dann nennt man den Prozess $\Pi ^{n}$ Kingmans Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Koaleszenz oder kurz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Koaleszenz.

Erläuterungen

Der Prozess kann als Prozess auf einem Stammbaum interpretiert werden, wobei man in der jüngsten Generation beginnt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi_0^n=\{\{1\},\{2\},\{3\},\dots,\{n-1\},\{n\}\}} ,

und an einem Zeitpunkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} endet, wenn es nur noch ein Cluster gibt

$\Pi _{T}^{n}=\{\{1,2,3,\dots ,n\}\}$.

Jeder Block verschmilzt mit Rate $1$, egal wie groß er ist. Wegen der Endlichkeit von $\Pi ^{n}$ haben die Markov-Ketten alle die gleiche endlich-dimensionale Verteilung.

Konsistenz

Betrachtet man die Restriktion auf ${\mathcal {P}}^{m}$ mit $m<n$, so erhält man den Prozess $\Pi ^{m,n}$, dessen Verteilung gerade die Verteilung von Kingmans $m$-Koaleszenz ist und somit unabhängig von $n$.

Kingmans Koaleszenz

Es existiert ein eindeutiger Prozess $(\Pi _{t})_{t\geq 0}$ auf ${\mathcal {P}}$, so dass die Restriktion auf ${\mathcal {P}}_{n}$ eine Kingman-$n$-Koaleszenz ist. $(\Pi _{t})_{t\geq 0}$ nennt man Kingmans Koaleszenz.

Big Bang: von ∞ zu n

Eine Besonderheit von Kingmans Koaleszenz ist, dass sie zwar in einer unendlichen Menge von Singletons startet, aber nach jeder Zeit $t>0$ fast sicher in einer Partition mit endlich vielen Blöcken landet.

Sei $N_{t}$ die Anzahl Blöcke von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi_t} . Mit $E$ bezeichnet man das Ereignis $E:=\{t>0,N_{t}<\infty \}$. Dann gilt $\mathbb {P} (E)=1$.

Heuristisch lässt sich das damit erklären, dass die Zeit des Überganges $n\to n-1$ eine Exponentialvariable mit $\lambda ={\tfrac {n(n-1)}{2}}$ ist. Für $n$ sehr groß, gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda\approx \frac{n^2}{2}} , somit verhält sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N_t} ungefähr wie die Lösung folgender Differentialgleichung: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u'(t) = -\tfrac{u(t)^2}{2}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u(0)=\infty} . Die Lösung dieser Differentialgleichung ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u(t)=2/t} , welche endlich für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t>0} ist, aber unendlich für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t=0} .