Topicos Avanzados en Ing. Mat

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

Announcements and other information about the class can be found here. A PDF copy of the course program can be found here: IMT_3800.pdf