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 linear algebra: matrix etc.
Reference: