Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

...Irrfahrten auf Graphen zu beschreiben und zu analysieren

...den Zusammenhang zwischen der Geometrie des Graphen und dem Langzeitverhalten der Irrfahrt zu beschreiben, insbesondere

...Rekurrenz und Transienz der Irrfahrt durch die elektrischen Eigenschaften des Graphen zu charakterisieren

...Fragen der Geschwindigkeit der Konvergenz zur stationären Verteilung (Mischungszeit, spektrale Lücke) für endliche Markovketten zu untersuchen

Irrfahrten und elektrische Netzwerke

• diskrete Drichlet-Form, Energie, effektive Widerstände/Leitfähigkeiten
• Charakterisierung des aszmptotischen Verhaltens mittels des Netzwerkwiderstands
• Gausssches freies Feld auf einem Graphen
• Loop-erased random walk
• Uniform random spanning tree: Wilson-Algorithmus, Burton-Pemantle-Theorem

Irrfahrten auf endlichen Graphen: Konvergenzgeschwindigkeit

• Mischungszeit
• Obere Schranken für die Mischungszeit: Pfadkopplung und gewichtete Abstände
• Spektrale Lücke, Variationsprinzip und Korrelationen in der Zeit
• Abschätzungen für die spektrale Lücke: geometrische Vergleichsmethoden
• Das Cutoff-Phänomen

Vortrag und Übungsbeispiele

Prüfung

Grundkenntnisse aus Wahrscheinlichkeitstheorie und theorie stochastischer Prozesse, Markovketten