Split-Merge Processes on Graphs and Matrices

We consider a model of split-merge processes on intervals, more precisely a continuous version of a split-merge process on intervals and a discrete version, the latter having a natural number n as parameter. These processes are well known and quite famous in the literature. It is known that the discrete process converges to the continuous one in the sense of stationary distributions. In this thesis we establish a kind of convergence which involves the finite dimensional distributions. Furthermore, we define a new model of split-merge processes which act on a more complex state space and can be seen as a generalization of the processes on intervals. More precisely, the processes act on weighted graphs. Since each weighted graph can be described by a matrix, we can also think of the process as if it would act on matrices. The idea of such a process is that at each time step we either merge two nodes into one or split one node into two. Then, the weights are updated in an adequate way. In this model, we equip a split-merge process with a parameter, which describes how to update the weights in case of a split. It turns out that for some parameters the resulting process is isomorphic to the continuous or discrete process on intervals, respectively. So we easily can derive properties for these processes. Moreover, we show that for a certain class of parameters the resulting processes might not be isomorphic to one of the interval model, but still converge to the process that is isomorphic to the continuous process on intervals.

Wir betrachten ein Modell bestehend aus Split-Merge Prozessen auf Intervallen. Genauer gesagt, betrachten wir eine stetige Version und eine diskrete Version eines Split-Merge Prozesses auf Intervallen, wobei die diskrete Version eine natürliche Zahl n als Parameter hat. Diese Prozesse wurden in der Literatur bereits ausführlich studiert. Zum Beispiel ist bekannt, dass beide Prozesse eine stationäre Verteilung haben und die zu dem diskreten Prozess gehörige stationäre Verteilung gegen die des stetigen Prozesses konvergiert. In dieser Arbeit zeigen wir, dass zudem die Prozesse selbst konvergieren in dem Sinne, dass die endlichdimensionalen Verteilungen des diskreten Prozesses gegen die des stetigen Prozesses konvergieren. Zudem definieren wir ein Modell aus Split-Merge Prozessen auf einem Raum mit mehr Struktur, genauer gesagt auf dem Raum der gewichteten vollständigen Graphen. Unter bestimmten Voraussetzungen können diese Prozesse als eine Verallgemeinerung der Prozesse auf Intervallen angesehen werden. Jeder gewichtete vollständige Graph kann als Matrix dargestellt werden. Aus diesem Grund können wir einen Split-Merge Prozess auf Graphen auch als Split-Merge Prozess auf Matrizen ansehen. Die Idee bei einem Split-Merge Prozess auf Graphen oder Matrizen ist, dass wir in jedem Schritt entweder zwei Knoten zusammenfügen (mergen) oder einen Knoten in zwei aufteilen (splitten) und nach dem Schritt die Gewichte auf eine passende Weise ändern. Wir versehen einen solchen Prozess mit einem Parameter, der angibt auf welche Weise das Gewicht nach einem Split aufgeteilt werden soll. Wir zeigen, dass für gewisse Parameter die entstehenden Prozesse isomorph zu dem jeweiligen Prozess auf Intervallen sind, sodass wir für diese auch schon Eigenschaften von den Prozessen auf Intervallen übertragen können. Außerdem zeigen wir für eine gewisse Klasse von Parametern, für die die entstehenden Prozesse vielleicht nicht isomorph zu Prozessen aus dem Intervall Modell sind, dass die zugehörigen Prozesse aber trotzdem gegen den Prozess konvergieren, der isomorph zu dem stetigen Prozess auf Intervallen ist.