Kingmans Koaleszenz

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

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

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

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

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

${\displaystyle 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 ${\displaystyle \Pi ^{n}}$ Kingmans ${\displaystyle n}$-Koaleszenz oder kurz ${\displaystyle n}$-Koaleszenz.

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

${\displaystyle \Pi _{0}^{n}=\{\{1\},\{2\},\{3\},\dots ,\{n-1\},\{n\}\}}$,

und an einem Zeitpunkt ${\displaystyle T}$ endet, wenn es nur noch ein Cluster gibt

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

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

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

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

Sei ${\displaystyle N_{t}}$ die Anzahl Blöcke von ${\displaystyle \Pi _{t}}$. Mit ${\displaystyle E}$ bezeichnet man das Ereignis ${\displaystyle E:=\{t>0,N_{t}<\infty \}}$. Dann gilt ${\displaystyle \mathbb {P} (E)=1}$.

Heuristisch lässt sich das damit erklären, dass die Zeit des Überganges ${\displaystyle n\to n-1}$ eine Exponentialvariable mit ${\displaystyle \lambda ={\tfrac {n(n-1)}{2}}}$ ist. Für ${\displaystyle n}$ sehr groß, gilt ${\displaystyle \lambda \approx {\frac {n^{2}}{2}}}$, somit verhält sich ${\displaystyle N_{t}}$ ungefähr wie die Lösung folgender Differentialgleichung: ${\displaystyle u'(t)=-{\tfrac {u(t)^{2}}{2}}}$ mit ${\displaystyle u(0)=\infty }$. Die Lösung dieser Differentialgleichung ist ${\displaystyle u(t)=2/t}$, welche endlich für jedes ${\displaystyle t>0}$ ist, aber unendlich für ${\displaystyle t=0}$.