Asymptotische Eigenschaften von Irrfahrten auf Graphen

Das Thema "Irrfahrten" ("Random walks") ist angesiedelt zwischen Wahrscheinlichkeitstheorie, Potentialtheorie, harmonischer Analyse, Geometrie, Graphentheorie und Algebra. Die Schoenheit des Themas begruendet sich in dieser Verbindung von verschiedenen Gebieten sowohl in der Denkweise als auch bei den zur Anwendung kommenden Methoden . Irrfahrten sind Zufallsprozesse (Markovketten) die an eine gegebene (geometrische oder algebraische) Struktur des zugrundeliegenden Zustandsraumes angepasst sind, auf dem sie sich "abspielen``. Die Strukturen, welche hier untersucht werden sind diskrete, unendliche Graphen und Gruppen. Aus wahrscheinlichkeitstheoretischer Sicht ist die Fragestellung, welchen Einfluss die spezifische Natur der Struktur auf verschieden Aspekte des Verhaltens der Irrfahrt hat, wie etwa Transienz/Rekurrenz, Asymptotik von Rueckkehrwahrscheinlichkeiten, Fluchtgeschwindigkeit und Konvergenz gegen Fernpunkte im Unendlichen, und harmonische Funktionen. Umgekehrt sind Irrfahrten auch ein Mittel, um die Struktur von Graphen, Gruppen und verwandten Oblekten zu verstehen und zu beschreiben. Die Zielsetzung des gegenstaendlichen Projektes ist das Studium spezifischer Aspekte von Irrfahrten vor allem auf Baeumen und baumartigen Strukturen der folgenden Arten: (A) Baeume mit endlichen vielen Verzweigungstypen, darunter auch die sogenannten "Kamm-Gitter", (B) eine allgemeinere Klasse von "kontextfreien" Graphen, (C) transitive Graphen mit unendlich vielen Enden, (D) Produkte gewisser Baeume, (E) die Diestel-Leader-Graphen. Die spezifischen Aspekte sind: (a) das asymptotische Verhalten von Uebergangswahrscheinlichkeiten, (b) das asymptotische Verhalten der Greenschen und Martinschen Kerne und der Martinsche Rand, (c) das raeumliche Verhalten von Trajektorien von Irrfahrten, (d) "internal diffusion limited aggregation" (unzureichend uebersetzt als: Aggregation durch Diffusion von Innen).

Eine Irrfahrt (random walk) ist ein Zufallsprozess auf einem Graphen (Netzwerk), wo sich ein Partikel (walker) zufällig von Punkt zu Punkt bewegt. Der Zufall wird hierbei durch eine Übergangsmatrix beschrieben. Bei gegebener aktueller Position gibt diese die Wahrscheinlichkeiten an, mit denen sich das Partikel im nächsten Schritt zu einem der anderen Punkte bewegt. Es wird vorausgesetzt, dass diese Übergangswahrscheinlichkeiten an die zugrunde liegende Graphenstruktur durch fallweise zu spezifizierende Bedingungen angepasst sind. Das generelle Thema des Projektes ist das Studium des Zusammenhanges zwischen (geometrischen, kombinatorischen oder algebraischen) Eigenschaften des Graphen (der hier stets unendlich viele Punkte hat) und probabilistischen sowie analytischen Eigenschaften der Irrfahrt: was können wir aus der Art der Struktur über das Verhalten des Zufallsprozesses schließen, und umgekehrt, was folgern wir aus Eigenschaften des letzteren über die zugrunde liegende Struktur ? Der interessierte Leser kann einen Einführungsartikel von Woess sowie einen anspruchsvolleren Überblick von Saloff-Coste (publiziert in den Notices of the A.M.S.) lesen, die beide online zugänglich sind unter www.math.tugraz.at/~woess/#research , oder die Monographie von Woess, "Random Walks on Infinite Graphs and Groups", Cambridge Univ. Press, 2000. Von den Resultaten des Projektes möchte ich hier das Thema der "lamplighter" Irrfahrten näher beschreiben. Zusätzlich zu der Bewegung auf dem Graphen befindet sich in jedem Punkt eine "Lampe". Anfangs sind alle Lampen "ausgeschaltet", und während sich das Partikel (der "Lampenanzünder") bewegt, wird die Lampe am aktuellen Punkt nach dem Zufallsprinzip ein- oder ausgeschaltet.Um diesen Zufallsprozess zu beschreiben, muss man einen übergeordneten "lamplighter"-Graphen betrachten, der sowohl die aktuelle Position des Partikels beschreibt wie auch die Konfiguration der gerade eingeschalteten Lampen. In der typischen Situation wo der Basisgraph der zweseitig unendliche Pfad ist, gelang im Projekt ein kleiner Durchbruch dank einem genauen Verständins der Geometrie des zugeordneten "lamplighter"-Graphen: Es ist ein Diestel-Leader-Graph, das horozyklische Produkt zweier homogener Bäume. Das hat es uns möglich gemacht, die harmonischen Funktionen (d.i., die Potentialtheorie) der Irrfahrt über den Martinrand genau zu beschreiben. Weiters haben wir eine explizite Methode erarbeitet, um das Spektrum des Übergangsoperators und die Asymptotik der n-Schritt- Übergangswahrscheinlichkeiten zu berechnen. Dies wurde für Diestel-Leader-Graphen gemacht, und in der Folge haben wir horozyklische Produkte einer beliebigen Zahl homogener Bäume eingeführt und eine Vielzahl interessanter Eigenschaften nachgewiesen. Eine ist, dass der Übergangsoperator immer ein pures Punktspektrum hat. Weitere "highlights" des Projektes betreffen Co-Wachstum von Graphen und Irrfahrten ohne Umkehrschritte, sowie die Asymptotik von "random walks" auf einer Klasse von Bäumen mit "fraktaler" Struktur.