Stochastische Abelsche Netzwerke und Rotor Wanderungen

Das vorliegende Projekt widmet sich der Untersuchung zweier Modelle (Irrfahrten und Rotor- Router Wanderungen) auf unendlichen Graphen. Ziel ist ein besseres Verständnis der geometrischen und strukturellen Eigenschaften der Graphen welche die Eigenschaften der Modelle bestimmen. Die in diesem Forschungsfeld benützten Methoden liegen einem Kreuzungspunkt vieler mathematischer Disziplinen (Wahrscheinlichkeitstheorie, Algebra, Graphentheorie, Kombinatorik, Theoretische Informatik). Im folgenden werden die geplanten Forschungsprobleme kurz umrissen. Rotor-Router Wanderungen (RRW). Informell kann eine Rotor-Router Wanderung auf einem Graphen wie folgt beschrieben werden. Jeder Knoten des Graphen wird mit einem Richtungspfeil (dem Rotor) versehen.Dieser Richtungspfeil bestimmtdie Bewegungsrichtung eines Teilchen das sich auf diesem Knoten befindet. Nach dem ein Teilchen von einem Knoten ausgesandt wurde wird der Rotor nach einer vorgegebenen deterministischen Art verändert. Die so erzeugte vollkommen deterministische Wanderung teilt sich viele Eigenschaften mit klassischen Irrfahrten, aber es gibt auch subtile Unterschiede die vom Graphen auf dem die Wanderungen stattfinden abhängen. Ich möchte diese Gemeinsamkeiten und Unterschiede im Detail auf folgenden Arten von Graphen untersuchen: Galton-Watson Bäumen, freien Produkten von endlichen Graphen und Lamplighter Graphen. Stochastische Abelsche Netzwerke (SAN). Ein Abelsches Netzwerk ist ein Netzwerk von Automaten, ähnlich wie ein zellulärer Automat, mit der zusätzlichen Eigenschaft, dass die einzelnen Automaten asynchron aktualisiert werden können, und der finale Zustand des Netzwerkes nicht von der Ordnung in der die Automaten ihre Daten verarbeiten abhängt. Die oben vorgestellte Rotor-Router Wanderung ist ein Beispiel eines solchen Abelschen Netzwerkes, wobei jeder Knoten im Graphen einen Automaten mit Rotor als internen Zustand darstellt. Die Abstrakte Theorie der Abelschen Netzwerke wurde erst kürzlich von BOND und LEVINE begründet. Ein stochastisches Abelsches Netzwerk ist ein Abelsches Netzwerk in dem die Übergangsfunktionen der einzelnen Automaten von einem Wahrscheinlichkeitsraum abhängen können. Eine Reihe bekannter Modelle der statistischen Physik kann als stochastisches Abelsches Netzwerk formalisiert werden: Markovketten, Verzweigende Irrfahrten, Internal DLA, Aktivierte Irrfahrten oder stochastische Sandhaufen. Zusammen mit LEVINE planen wir die Entwicklung der Grundlagen einer Theorie der stochastischen Abelschen Netzwerke, um die genannten Modelle auf eine gemeinsame mathematische Basis zu stellen. Ein Startpunkt dabei ist die Analyse von sogenannten lokal Markov`schen Wanderungen.

Ein Abelsches Netzwerk ist ein theoretisches Modell eines parallelen Computers bestehend aus einem Netzwerk von Prozessoren die miteinander kommunizieren indem sie Nachrichten an ihre Nachbarn im Netzwerk senden. Ein Abelsches Netzwerk unterscheidet sich von den ublichen parallelen Computermodellen, durch die Eigenschaft dass die Ordnung in der die Prozessoren ihre eingehenden Nachrichten verarbeiten keine Auswirkung auf den Endzustand des Netzwerkes, und somit auch auf das Ergebnis der Berechnung, hat. Das bedeutet dass die einzelnen Prozessoren ihre eingehenden Nachrichten so schnell wie möglich verarbeiten können ohne dass eine Synchronisation zwischen den Prozessoren notwendig ist um die Korrektheit der Berechnung zu gewährleisten. Diese sogenannte Abelsche Eigenschaft legt sehr starke Einschränkungen an die Art der Prozessoren im Netzwerk fest. Obwohl bekannt ist, dass zum Beispiel bestimmte Klassen von Optimierungs-Problemen durch Abelsche Netzwerke gelöst werden können, ist die volle Klasse von Problemen die von Abelschen Netzwerken berechnet werden können derzeit noch nicht bekannt.In meiner Forschung beschäftige ich mich hauptsachlich mit einem der einfachsten Beispiele eines Abelschen Netzwerkes, dem sogenannten Rotor-Router Modell. Im Rotor-Router Modell gibt es nur eine Art von Nachricht die die Prozessoren austauschen können, und jeder Prozessor sendet fur jede eingehende Nachricht genau eine Nachricht an einen seiner Nachbarn. Wir stellen uns die Nachrichten als Teilchen vor die durch das Netzwerk wandern. Die Prozessoren senden jedes ankommende Teilchen zum einem ihrer Nachbarn in einer vorgegebenen Reihenfolge. Der Weg den ein Teilchen durch das Netzwerk nimmt nennen wir Rotor-Router Wanderung. Die Abelsche Eigenschaft besagt in diesem Fall, dass es keinen Unterschied macht ob ein Teilchen nach dem anderen durch das Netzwerk gerouted wird, oder ob sich alle Teilchen gleichzeitig im Netzwerk befinden.Ein weiteres sehr gut untersuchtes Modell von Wanderungen in Netzwerken sind die sogenannten Irrfahrten, bei denen die Richtung des nächsten Schrittes eines Teilchens im Netzwerk zufällig (zum Beispiel durch den Wurf einer Münze) bestimmt wird. Rotor-Router Wanderungen und Irrfahrten weisen viele ähnliche Eigenschaften auf. Ich beschäftige mich hauptsachlich mit den Unterschieden zwischen diesen beiden Arten von Wanderungen. Es ergeben sich zum Beispiel sehr starke Unterschiede wenn man das Langzeitverhalten der beiden Modelle auf unendlichen Bäumen (das sind Netzwerke ohne geschlossene Kreise) untersucht.Eines der Hauptergebnisse dieses Projektes, in einer gemeinsamen Arbeit mit Sebastian Müller und Ecaterina Sava-Huss, untersucht das Langzeitverhalten von Rotor-Router Wanderungen auf einer bestimmten Art von zufälligen Bäumen. Wir zeigten dass Rotor-Router Wanderungen unendlich oft an Ihren Startpunkt zurückkehren wenn die Durchschnittliche Anzahl von Nachbarn im Baum den Wert 3 nicht überschreitet. Dies steht in Gegensatz zum Verhalten von Irrfahrten. Es war bereits bekannt dass Irrfahrten auf denselben Netzwerken nur endlich oft zurückkehren. Dieses Ergebnis wird hoffentlich auch zu einem besseren Verständnis des Langzeitverhaltens von Rotor-Router Wanderungen auf anderen Netzwerken, wie zum Beispiel dem wichtigen Fall der unendlichen Gitter, beitragen. Gitter kann man sich vorstellen als ein unendliches möglicherweise höherdimensionales regelmäßiges Straßennetz, wie man es von Manhattan kennt. Ein berühmtes Theorem von George Polya aus dem Jahr 1921 besagt dass Irrfahrten in einem Gitter der Dimension 3 oder hoher mit positiver Wahrscheinlichkeit nicht an ihren Startpunkt zurückkehren. Über das Verhalten von Rotor-Router Wanderungen auf den Gittern ist derzeit noch nichts bekannt.