Detailansicht
Mixing and cover time profiles for random walks on graphs
Lucas Teyssier
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doktoratsstudium NAWI aus dem Bereich Naturwissenschaften (DissG: Mathematik)
Betreuer*in
Nathanaël Berestycki
DOI
10.25365/thesis.74750
URN
urn:nbn:at:at-ubw:1-10040.24816.617514-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Doktorarbeit, tragen wir zur quantitativen Theorie der Zufälligen Irrfahrten auf Graphen bei. Wir betrachten zunächst das Problem der Überdeckungszeit. Auf endlichen knoten-transitiven Graphen mit beschränktem Grad, finden wir eine notwendige und hinreichende Bedingung dafür, dass die korrekt skalierte Überdeckungszeit asymptotisch Gumbel-Schwankungen hat. Genauer gesagt, gilt dies dann und nur dann, wenn $\mathrm{Diam}(\Gamma)^2 = o(n/\log n)$, wo $n = |\Gamma|$. Überraschenderweise bezieht sich die Bedingung also ausschließlich auf die globale Geometrie des Graphen. Außerdem beweisen wir, dass diese Bedingung äquivalent zur Dekorrelation der unüberdeckten Menge ist. Die Argumente stützen sich auf die jüngsten Durchbrüche von Tessera und Tointon zu finitären Versionen vom Satz von Gromov über Gruppen mit polynomialem Wachstum, die wir in starke Schranken für den Wärmeleitungskern umwandeln. Auf technischer Ebene besteht die wichtigste Neuerung darin, verfeinerte quantitative Schätzungen für eine exponentielle Annäherung der Trefferzeiten zu erhalten, die erstmals von Aldous und Brown vorgeschlagen wurden. Im nächsten Teil untersuchen wir das Problem der Mischzeiten, hauptsächlich mit darstellungstheoretischen Techniken. Zunächst finden wir eine Verbesserung des Lemmas der oberen Schranke von Diaconis und Shahshahani, die für die Untersuchung von Grenzprofilen geeignet ist. Kombiniert man dies mit einer neuen Identität, die die Zeichen der symmetrischen Gruppe einbezieht, kann man das Schnittprofil für zufällige Transpositionen finden. Dieses lässt einen expliziten Ausdruck in Form der Poisson-Verteilungen zu. Schließlich untersuchen wir ein Analogon der Brownschen Bewegung auf freien orthogonalen Quantengruppen. Wir finden dessen Schnittprofil, das freie Poisson-Verteilungen und die Halbkreisverteilung involviert.
Abstract
(Englisch)
In this thesis, we contribute to the quantitative theory of random walks on graphs. We first consider the cover time problem. On finite vertex-transitive graphs of bounded degree, we find a necessary and sufficient condition for the properly rescaled cover time to have asymptotically Gumbel fluctuations. More precisely, this holds if and only if $\mathrm{Diam}(\Gamma)^2 = o(n/\log n)$, where $n = |\Gamma|$. Surprisingly, the condition is therefore purely in terms of the global geometry of the graph. Furthermore, we prove that this condition is equivalent to the decorrelation of the uncovered set. The arguments rely on recent breakthroughs by Tessera and Tointon on finitary versions of Gromov's theorem on groups of polynomial growth, which we leverage into strong heat kernel bounds. At the technical level the main innovation consists in obtaining refined quantitative estimates for an exponential approximation of hitting times, first put forward by Aldous and Brown. In the next part we study the problem of mixing times, mostly with representation theoretic techniques. First, we find an improvement of the Diaconis--Shahshahani upper bound lemma, which is suitable for investigating limit profiles. Combining this with a novel identity involving the characters of the symmetric group, this allows us to find the cutoff profile for random transpositions. This admits an explicit expression in terms of Poisson laws. Finally, we study an analogue of Brownian motion on free orthogonal quantum groups. We find its cutoff profile, which involves free Poisson distributions and the semi-circle law.
Schlagwörter
Schlagwörter
(Deutsch)
Wahrscheinlichkeitstheorie Markov-Ketten Mischzeiten Deckzeiten Darstellungstheorie
Schlagwörter
(Englisch)
Probability theory Markov chains mixing times cover times representation theory
Autor*innen
Lucas Teyssier
Haupttitel (Englisch)
Mixing and cover time profiles for random walks on graphs
Paralleltitel (Deutsch)
Mischzeit- und Überdeckungszeit-Profile für zufällige Irrfahrten auf Graphen
Publikationsjahr
2023
Umfangsangabe
153 Seiten
Sprache
Englisch
Beurteiler*innen
Perla Sousi ,
Persi Diaconis
Klassifikation
31 Mathematik > 31.70 Wahrscheinlichkeitsrechnung
AC Nummer
AC16992736
Utheses ID
66967
Studienkennzahl
UA | 796 | 605 | 405 |