Program
Introduction to Markov chain mixing times
Student No.:50
Time:Wed/Fri 10:10-12:00, 2015-07-22 ~ 2015-08-14
Instructor:Hao Wu  [Department of Mathematics, MIT]
Place:Conference Room 3, Floor 2, Jin Chun Yuan West Building
Starting Date:2015-7-22
Ending Date:2015-8-14

 

 

Description:

Markov chain plays an active and diverse interdisciplinary role in computer science, engineering, physics, statistics, and many other areas. The classical theory of Markov chains studied the rate of convergence to stationarity. In the recent decades, people become interested in chains with large state spaces, a different asymptotic analysis has emerged. Some target distance to the stationary distribution is prescribed; the number of steps required to reach this target is called the mixing time of the chain.

This mini course is an introduction to Markov chain mixing times. The goal is to understand how the mixing time grows as the size of the state space increases. 

There will be eight lectures. 

Lecture 1. Introduction to Markov chains 

Lecture 2. Stationary distribution

Lecture 3. Introduction to mixing times

Lecture 4. Upper bounds on mixing times

Lecture 5. Lower bounds on mixing times

Lecture 6. Random walk on networks

Lecture 7. Hitting times

Lecture 8. Summary on mixing times

 

 

Prerequisite:

Basic knowledge in probability theory: conditional expectation etc.

Basic knowledge in linear algebra: matrix etc.

 

 

Reference:

Markov chains and mixing times, by David A. Levin, Yuval Peres, Elizabeth L. Wilmer.