# 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:
* $\Pi _{0}^{n}$ ist die triviale Partition in Singletons.
* $\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 $n$-Koaleszenz oder kurz $n$-Koaleszenz.

### Erläuterungen

Der Prozess kann als Prozess auf einem Stammbaum interpretiert werden, wobei man in der jüngsten Generation beginnt
    $\Pi _{0}^{n}=\{\{1\},\{2\},\{3\},\dots ,\{n-1\},\{n\}\}$,
und an einem Zeitpunkt $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 $\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 $\lambda \approx {\frac {n^{2}}{2}}$, somit verhält sich $N_{t}$ ungefähr wie die Lösung folgender Differentialgleichung: $u'(t)=-{\tfrac {u(t)^{2}}{2}}$ mit $u(0)=\infty$. Die Lösung dieser Differentialgleichung ist $u(t)=2/t$, welche endlich für jedes $t>0$ ist, aber unendlich für $t=0$.