Programa del curso
Markov Chains: Mixing Times and Applications
Announcements and other information about the class can be found here.
Instructor: Anastasios Matzavinos, firstname.lastname@example.org
Instructor's office hours: Tue 2:00 pm - 3:20 pm or by appointment.
Course description: The theory of Markov chains has a wide range of applications in computer science, statistical physics, engineering, data science, and many other areas. For instance, when investigating the complexity of Markov Chain Monte Carlo (MCMC) algorithms in statistics, one is naturally led to the problem of estimating the time it takes for a Markov process to reach stationarity. Our main focus this semester will be on developing the theoretical machinery that enables us to compute such "mixing times" as a function of the size and geometry of the underlying state space. Topics covered will include the basic theory of finite Markov chains, the total variation distance, coupling estimates of mixing times, ergodicity, random walks on networks, spectral representations, Dirichlet forms, the transportation metric, and path coupling, among others. Along the way, we will also discuss and analyze various MCMC approaches to sampling and optimization, as well as certain interacting particle systems, which are of interest in computer science and statistical physics.
Learning outcomes: Upon successful completion of this course, students will be able to demonstrate the following competencies: (i) an understanding of the modern theory of finite Markov chains, (ii) a thorough understanding of the complexity of MCMC sampling and optimization algorithms in data science and statistics, and (iii) an ability to engage with research literature.
References: Our main reference will be the book by Levin and Peres on Markov chains and mixing times There is also an excellent set of notes by Aldous and Fill that covers a lot of the material we will be discussing throughout the semester.
Grading policy: The final grade will be based on homework assignments and a final exam.
Homework assignments: Homework problems will be handed out on a regular basis. Discussion of homework assignments with other students is encouraged, but what is handed in should be your own work.
Course content: We will cover the following topics.
- Introduction to finite Markov chains (irreducibility, aperiodicity, reversibility, stationary distributions)
- Metropolis and Glauber chains
- Markov chain mixing (total variation distance, convergence, ergodicity)
- Coupling estimates and mixing times
- Strong stationary times
- Random walks on networks
- Hitting times and cover times
- Spectral representations
- Dirichlet forms
- Optimal transport and path couplings
- The Propp-Wilson algorithm
La página del plan de estudio muestra una vista de tabla del programa del curso y lo básico de la calificación del curso. Puede agregar otros comentarios, notas o ideas que tenga acerca de la estructura del curso, políticas del curso o cualquier otra cosa.
Para agregar algunos comentarios, haga clic en el vínculo de "Editar" en la parte superior.
Resumen del curso:
|Fecha de entrega||Detalles||Hora de entrega|