Department of Mathematics and Statistics
Concordia University

Fall 2011

MAST 679C/MAST 881S: Mixing Times for Markov Chains

TJ 12:15-13:30, LB-655 (SGW)

 
Instructor: Lea Popovic
Office: LB 921-07 (SGW)
Phone: (514) 848-2424 Ext 5854
email: lpopovic@mathstat.concordia.ca 

Office Hours: after class and by appointment

Course Outline

This course will present a modern approach to dynamics of Markov chains. Mixing time is the number of steps that is required for a Markov chain to roughly reach its stationary distribution. Due to a growing interest in Markov chains on large state spaces, asymptotic results for their dynamics as the state space increases have become very relevant for many applications. In this course we will examine the rate fo convergence of Markov chains to their stationary distribution as a function of the size and geometry of the state space. Key tools will include: coupling, strong stationary times, and spectral methods. The course will include many examples and will provide a brief introduction to: random walks on graphs, electrical networks, the Metropolis algorithm, some models of statistical mechanics, and others.
The main part of the course will cover:
  • Finite Markov chain basic properties
  • Classical chains: random walks, birth-and-death chains
  • Markov chain Monte Carlo: Metroplis and Galuber dynamics
  • Mixing Times: Total Variation distance, coupling, ergodicity
  • Random walks on Networks and reversible chains
  • Eigenvalues and spectral representation

Prerequisites

Only an introductory course in probability and Markov chains and some Linear Algebra is required in order to follow this course.

Text

"Markov Chains and Mixing Times" by Y.Peres, D.Levin, E.Wilmer (AMS, 2008). You can find a pdf version of the text here.

Grading

Homework will be assigned approximately once every two weeks, during lecture. Students are encouraged to work together on homework problems, however each student must write up the homework set on their own. There will be a take-home midterm exam at the end of October, and a take-home final exam handed out in the last week of class and due a week later. Each student must work on their own on the exams. The final grade will be evaluated using: Homework assignments 40%, Midterm exam 20%, Final exam 40%.

Important Dates

No class on Oct 27  Midterm exam  due Nov 3

NEW: Extra office hours   Dec 8: 3-5pm,   Dec 12: 3-5pm

NEW: Final exam due Dec 12

Lecture Schedule     Homework Schedule