On July 30th, 2024, due to an important database update, there will be service interruptions in the Student Self-Service and Workforce Management areas between 8 AM and 11 AM. Thank you for your understanding.

105.724 AKWTH Random walks on graphs This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2023S 2020W 2020S

2023S, VO, 3.0h, 4.5EC

Properties

• Semester hours: 3.0
• Credits: 4.5
• Type: VO Lecture
• Format: Presence

Learning outcomes

After successful completion of the course, students are able to...

...describe and analyze random walks on graphs

...describe the relationship between the geometry of the graph and the long term behavior of the random walk, in particular

...characterize recurrence and transience in terms of the electrical properties of the graph

...investigate questions of convergence towards the stationary distribution (mixing times, spectral gap) for finite-state Markov chains

Subject of course

This course is about Markov chains (mostly: reversible) on (large or infinite) graphs, and the focus will be on asymptotic properties, like recurrence and transience, and the approach to the stationary measure in the large-time limit. I will make connections to several central topics in (mathematical) statistical mechanics: the Gaussian free field, loop-erased random walks and uniform spanning trees, Glauber dynamics of the Ising model…

Part I Random walks and electric networks

• Discrete Dirichlet form, energy, effective resistances/conductances
• Characterization of the asymptotic behavior via the network resistance
• Gaussian Free Field on a graph
• Loop-erased random walk
• Uniform random spanning tree of a graph: Wilson’s algorithm and determinantal correlations (Burton-Pemantle theorem)

Part II Random walks on finite graphs: speed of convergence

• Mixing time T mix (reversible and non-reversible random walks)
• T mix upper bounds: path coupling and weighted distances
• Spectral gap, variational principle and time correlations
• Bounding the spectral gap: geometric comparison methods
• The cutoff phenomenon

Teaching methods

Lecture and homework problems

Oral

Course dates

DayTimeDateLocationDescription
Mon09:00 - 12:0006.03.2023 - 26.06.2023Seminarraum 107/1 AKWTH Random walks on graphs
Wed14:00 - 16:0031.05.2023Seminarraum 127 AKWTH Random walks on graphs
Tue14:00 - 16:0006.06.2023Seminarraum 127 AKWTH Random walks on graphs
AKWTH Random walks on graphs - Single appointments
DayDateTimeLocationDescription
Mon06.03.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon13.03.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon20.03.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon27.03.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon17.04.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon24.04.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon08.05.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon15.05.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon22.05.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Wed31.05.202314:00 - 16:00Seminarraum 127 AKWTH Random walks on graphs
Mon05.06.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Tue06.06.202314:00 - 16:00Seminarraum 127 AKWTH Random walks on graphs
Mon12.06.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon19.06.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs
Mon26.06.202309:00 - 12:00Seminarraum 107/1 AKWTH Random walks on graphs

Exam

Course registration

Begin End Deregistration end
13.02.2023 08:00 01.04.2023 08:00

Curricula

Study CodeObligationSemesterPrecon.Info
860 GW Optional Courses - Technical Mathematics Mandatory elective

Literature

No lecture notes are available.

Previous knowledge

Basics of probability theory and stochastic processes and  of Markov Chains

English