COL863: Special Topics in Theoretical Computer Science
Topic: Rapid Mixing in Markov Chains
II semester: 2016-17
Amitabha Bagchi
Class Timings: Mon Wed 11AM, Th 12PM.
Room: LH 520.
Topics
Basic properties of Markov Chains; Some useful Markov Chains; Random walks; Markov Chain Monte Carlo (including Metropolis and Glauber dynamics chains); Total Variation Distance and Mixing; Coupling; Strong stationary times; Random walks on networks; Hitting times and Cover times; Algebraic view of Markov chains; the Transportation Metric and Path Coupling.
Background required: Elementary probability, some graph theory, linear algebra.
Texts
- D. A. Levin, Y. Peres, and E. Wilmer, Markov Chains and Mixing Times. Download here (Please download the 2nd edition). This book will be refered to as LPW on the rest of this page.
- D. Aldous and J. A. Fill. Reversible Markov Chains and Random Walks on Graphs. Unfinished monograph. 1999-2002. Available here.
Important: You are expected to have familiarised yourself with the material in Appendix A and read through Chap 1 of LPW before the first meeting of this class.
Course outline
All Chapter numbers refer to LPW. The bullet points in italics will be largely self-study.
- Intro to Finite Markov Chains (Chap 1).
- Classical Markov Chains (Chap 2).
- Random Walks on Networks (Chap 9), Hitting Times (Chap 10) and Cover Times (Chap 11).
- Intro to Markov Chain Mixing (Chap 4) and Coupling (Chap 5).
- Lower Bounds on Mixing Times (Chap 7).
- Eigenvalues of Markov Chains (Chap 12) and Comparison of Chains (Chap 13)
- The Transportation Metric and Path Coupling (Chap 14).
- Evolving Sets (Chap 17).
Refresher texts
Evaluation
There will be a self-study viva held in the 2nd week of the class (the week of 9-13 Jan) to determine the extent of preparation for the course. This will count for 20% of the grade. Those students who score below 50% in this exam will be advised to withdraw the class.
The remaining 80% will be given on the basis of 3-4 take-home exams.
Exams
Exam guidelines
- Latex only. All exams are to be submitted as a pdf file
created from latex source. No handwritten exams will be accepted.
- Moodle submission only. If you are registered in this
course you are registered in this course on moodle. Please only submit
your exam there the the appropriate upload link. If you
are not registered in the course and wish to submit the exam
you may email it to the TA Guntash Arora with cc to me.
- Collaboratation and Plagiarism
- You are expected to attempt all problems on your own.
- You may consult online or other resources. However if you find the solution
to one of the problems you are expected to not look at the
solution.
- You may discuss solution ideas. However if you have the entire
solution it is incumbent on you to not reveal the solution to
your fellow students.
- You may not copy or cut and paste any text from any source
whatsoever (your friends, the textbook, online, anything).
- If you need to
quote anything from anywhere a complete citation should be provided,
i.e., it should be possible for the grader to look up the source
easily.
- A violation of the copying rule (previous two bullet points) will
lead to very stringent action with no excuse for even a
minor-seeming violation and no opportunity to make up. This is an
800-level class and a high degree of integrity should be considered a prerequisite.
Amitabha
Bagchi