Asymptotische Eigenschaften von Irrfahrten auf Graphen#
Von
Univ.-Prof. Dipl.-Ing. Dr.rer.nat. Wolfgang Woess
Arbeitsgruppe Mathematik C des Instituts für Mathematik
Das FWF-Projekt „Asymptotic Properties of Random Walks on Graphs“ sowie das Schrödinger-Rückkehrprojekt „Spektralberechnung und nichtkommutative Wahrscheinlichkeitstheorie“ und das Marie Curie Fellowship „Internal Diffusion Limited Aggregation on Nonhomogeneous Structures“ sind in der Arbeitsgruppe C des Instituts für Mathematik C beheimatet. Im weitesten Sinne geht es um Wahrscheinlichkeitstheorie und Analysis auf diskreten Strukturen. „Random Walks“, zu Deutsch „Irrfahrten“, sind Zufallsprozesse, die sich auf Graphen (im Sinne der Kombinatorik), bzw. Gruppen (im Sinne der Algebra) abspielen. Im Mittelpunkt des Interesses steht das Studium und die Theorie des Zusammenhanges zwischen dem probabilistischen Verhalten sowie analytischen Kennzahlen dieser Prozesse und den geometrischen Eigenschaften der zugrundeliegenden Strukturen.
Bei Irrfahrten denken manche wohl zuerst an Homer und die Odyssee. Diese schöne Bezeichnung geht auf den berühmten ungarischen Mathematiker Georg Pólya zurück, der 1921 eine Arbeit unter dem Titel „Über eine Aufgabe der Wahrscheinlichkeitstheorie betreffend die Irrfahrt im Straßennetz“ in den Mathematischen Annalen veröffentlichte und damit diese Theorie begründete. Sie hat sich vor allem seit den 1950er Jahren in gewissen Wellenbewegungen der Mode entwickelt und seit etwa 1985 einen rasanten Aufstieg erlebt. Die Anwendungen reichen von der theoretischen Physik und Chemie über die Theorie der elektrischen Netzwerke bis zur Modellierung von Börsenspekulationen. Die hier verfolgten Projekte befassen sich mit der mathematischen Theorie.
Worum geht es nun in dieser Theorie? Zum Zweck einer einfachen Einleitung beginnen wir bei Pólya, und stellen uns ein unendliches, ebenes Straßennetz mit quadratischen Häuserblöcken vor (Abb. 1a). Ein Wanderer, bzw. Partikel beginnt in einem Kreuzungspunkt und wählt einen zufälligen unter den 4 benachbarten Kreuzungspunkten, zu dem er nun in einem „Schritt“ geht. Dort angekommen, verfährt er genauso, und zwar ohne sich zu erinnern, woher er gekommen war. Was geschieht auf lange Sicht ? Eine einfache Rechnung zeigt, dass der Wanderer mit Sicherheit immer wieder, unendlich oft, zum Ausgangspunkt zurückkommt - die Irrfahrt ist rekurrent. Stellen wir uns als nächstes ein dreidimensionales Straßennetz vor, in dem der Wanderer unter 6 Richtungen (N, S, O, W, oben, unten) wählt. Eine etwas kompliziertere Rechnung ergibt, dass in diesem Modell der Wanderer nur einige Male zum Ausgangspunkt zurückkehren wird und sich dann sozusagen in der unendlichen Weite des Raumes verliert, die Irrfahrt ist transient. Mathematiker wollen den drastischen Unterschied zwischen dem 2- und dem 3-dimensionalen Modell verstehen: indem sie das - zunächst einfache - Modell aus verschiedenen Blickwinkeln untersuchen und verallgemeinern, um so eine generelle Phänomenologie zu erarbeiten. Man betrachtet anstelle der einfachen quadratischen Straßennetze in 2, 3 oder d Dimensionen beliebige Straßennetze, sogenannte Graphen, die nicht mehr so homogen sein müssen, oder ggf. eine ganz andere Art von Homogenität (Struktur einer algebraischen Gruppe) aufweisen. Ein einfaches Beispiel ist der ebene Graph aus Abb. 1b (den man sich in allen Richtungen unendlich fortgesetzt vorstellen muss, wobei nach oben die Größe der Quadrate immer verdoppelt und nach unten immer halbiert wird).
Die Irrfahrt auf diesem Graphen ist in einem viel stärkeren Sinne transient als jene im 3-dimensionalen Straßennetz. Generell will man dann verstehen, welche Struktureigenschaften des Graphen für die Rekurrenz oder Transienz verantwortlich sind.
Abgesehen von dieser ersten Frage stehen viele andere charakteristische Eigenschaften dieser Zufallsprozesse im letzten Jahrzehnt im Fokus mathematischer Forschung. Es sei hier auf einen Übersichtssartikel von L. Saloff-Coste verwiesen (Notices Amer. Math. Soc. 48, No. 9, 2001), siehe http://www.cis.tugraz.at/mathc/woess/ saloff_notices.pdf
Im FWF-Forschungsprojekt “Asymptotic Properties of Random Walks on Graphs“ (Dauer: 3 Jahre, Beginn: 1.10.2002) arbeiten - neben dem Leiter - derzeit Herr Dr. Ronald Ortner und Frau Dr. Sara Brofferio. Es werden unter anderem die folgenden Fragestellungen untersucht:
a) Das asymptotische Verhalten von n-Schritt-Rückkehrwahrscheinlichen hängt unmittelbar von der Geometrie des Graphen ab. Es geht darum, die Art dieser Abhängigkeit besser zu verstehen. Besonders für Graphen von (algebraischen) Gruppen arbeiten verschiedene Forschungsgruppen intensiv an dieser Fragestellung. Zumeist werden Methoden der Funktionalanalysis verwendet, während die Gruppe an der TU Graz auf die Verwendung komplex-analytischer Methoden spezialisiert ist. (In diesem Bereich besteht auch eine Verbindung zum START-Projekt “Konkrete Mathematik“, Leiter: Ao.Prof. Dr. Peter Grabner.) Diese Methoden werden hier insbesondere auf freie Produkte mit Amalgamierung angewandt (Dr. Ortner).
b) Das räumliche Verhalten von Irrfahrten: Kann man genauer beschreiben, wie sich im transienten Fall das wandernde Partikel „im Unendlichen verliert“ ? D.h., man will mögliche „Richtungen“ beschreiben, denen dieses Abdriften folgen kann, und die zugehörigen Wahrscheinlichktsverteilungen bestimmen. Dies ist ein topologisches Problem (man sucht die sogenannte Martin-Komaptifizierung), das direkt mit der Potentialtheorie und dem Studium harmonischer Funktionen zusammenhängt. Dieser Themenbereich wird insbesondere für eine Klasse von Modellen zufällig fluktuierender Konfigurationen im Raum untersucht (Dr. Brofferio, Prof. Woess).
c) Internal diffusion limited aggregation (IDLA) ist ein Prozess, in dem immer wieder neue Partikel unabhängig voneinander am gleichen Ausgangspunkt eine Irrfahrt beginnen und sich am ersten noch nicht besetzten Punkt des Graphen festsetzen. Auf diese Art wird eine stetig anwachsende Zufallskonfiguration rund um den Startpunkt gebildet. Dieses Modell hat z.B. eine (besorgniserregende) Anwendung in der Modellierung der Emission radioaktiver Teilchen aus einem geborstenen Endlagerungsbehälter in die umliegende Sandschicht gefunden. Die primäre mathematische Fragestellung ist hier jene nach der asymptotischen Form der Konfiguration. Dies wurde für die eingangs (Pólya) erwähnten quadratischen Gitter in Ebene und Raum und ähnliche homogene Strukturen untersucht; die Konfiguration ist asymptotisch kugelförmig. Ein Ziel des Projektes ist es, anhand von - zunächst einfachen - Fallstudien ein Verständnis dieses Zufallsprozesses auf nichthomogenen Strukturen zu erzielen. Vorarbeiten hiezu sind Teil einer derzeit laufenden Diplomarbeit (Herr Huss), deren Inhalt eine Computersimulation von IDLA auf verschiedenen Graphen ist, so z.B. der ebene Comb lattice, in dem sich die Partikel nur auf der Grundlinie horizontal und sonst nur vertikal bewegen können, siehe hiezu die Abb. 2, aus der ersichtlich wird, dass die agglomerierte Konfiguration nach Emission von 100, 500, bzw. 1000 Partikeln immer mehr „diamantenförmig“ wird. Im Anschluss an diese Vorarbeit sollen deren Resultate im Rahmen des erstgenannten FWF-Projektes genauer und rigoroser mathematisch untersucht werden (Dissertant).
IDLA on non-homogeneous structures ist auch der Titel des Marie Curie PostDoc Fellowships, in das Frau Dr. Brofferio ab 1.3.2003 übergewechselt ist.
Teil des FWF-Projektes ist die internationale Kooperation mit Forschern von den Universitäten in Rennes, Lyon und Berkeley, der Technischen Hochschule in Stockholm und der Cornell University in Ithaca (N.Y.). So war im Oktober 2002 im Rahmen des Projektes Herr Prof. V. A. Kaimanovich aus Rennes zu Gast (Zusammenarbeit im Themenbereich b), und im Jänner/Februar 2003 Herr Prof. L. Saloff-Coste von der Cornell University als Gasprofessor hier (Zusammenarbeit im Themenbereich a).
Chronologisch das älteste unter den drei anfangs genannten Projekten ist das Schrödinger-Rückkehrstipendium von Herrn Dr. Lehner (Beginn: 1.7.2001, Dauer: 3 Jahre). Herr Dr. Lehner hat an der Université Paris 6 promoviert und ist einer der ersten jüngeren österreichischen Forscher, für den im Rahmen dieses FWF-Rückkehrprogrammes ein Projekt bewilligt wurde. Die nichtkommutative Wahrscheinlichkeitstheorie ist ein Teilgebiet der Funktionalanalysis. Im Rahmen des Projektes befasst sich Herr Dr. Lehner mit der Anwendung dieser Theorie auf die Berechnung des Spektrums von Faltungsoperatoren, also insbesondere jenen Operatoren, die die Übergangswahrscheinlichkeiten von Irrfahrten beschreiben. Die Abb. 3 stellt das Spektrum (und schattiert die Dichte des Spektralmaßes) eines nicht selbstadjungierten Faltungsoperators auf einem freien Produkt zweier Gruppen dar, deren Graph die Form eines unendlichen „Baumes“ hat.