!!!Asymptotische Eigenschaften von Irrfahrten auf Graphen
\\
Von

\\
__Univ.-Prof. Dipl.-Ing. Dr.rer.nat. Wolfgang Woess__\\

Arbeitsgruppe Mathematik C des Instituts für Mathematik


\\

[{Image src='0203_MATH_Asymptotische_Eigenschaften_von_Irrfahrten_auf_Graphen1.jpg' alt='Univ.-Prof. Dipl.-Ing. Dr.rer.nat. Wolfgang Woess'  caption='Wolfgang Woess' popup='false' width='77' height='100'}]

\\

%%small 
''© Forschungsjournal WS 2002/2003''
%%

\\

__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). 

[{Image src='0203_MATH_Asymptotische_Eigenschaften_von_Irrfahrten_auf_Graphen2.jpg' caption='Abb. 1a und Abb. 1b' class='image_right' width='300' height='125'}]

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).

[{Image src='0203_MATH_Asymptotische_Eigenschaften_von_Irrfahrten_auf_Graphen3.jpg' caption='Abb. 2' class='image_left' width='200' height='305'}]

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).

[{Image src='0203_MATH_Asymptotische_Eigenschaften_von_Irrfahrten_auf_Graphen4.jpg' caption='Abb. 3' class='image_right' width='300' height='223'}]

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.

\\