COL727: Rapid Mixing in Markov Chains
I semester: 2024-25
Amitabha Bagchi
Class Timings: Tu Fr 3:30PM.
Room: LH 521.
Topics
Basics of finite Markov chains; classical Markov Chains including Coupon Collection, Gambler's Ruin, Polya's urn, Birth and Death chains; Total Variation Distance; the Convergence Theorem; Mixing Time; bounding mixing time via couplings; bounding mixing time via strong stationary times; random walks on networks; bounding mixing time via hitting times; cover times; spectral bounds on mixing time; mixing time bounds via comparison between chains.
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.
Other references
Course Calendar
Topic listing is tentative and likely to change as we go along. Topics marked "Self study" are supposed to be read on your own.
Evaluation
- There will be only 4 take-home exams, each carrying 25% weight. The date for each of these exams is available in the course calendar. No midterm exam or major exam will be held during the institute's designated exam periods.
- Students scoring at least 20 marks but less than 30 marks will receive an E grade and be eligible for a remajor worth 25 marks (conditional on their having 75 percent attendance).
Exams
All submissions will be via gradescope. You may write by hand or latex your solutions. Please make sure you write your name on top of the first sheet of paper.
Please see: Guidelines for writing a proof, and also how to upload your paper to Gradescope.
- Minor 2. Download here. Posted 6 September 2024. Due on Gradescope by 11:55PM, 8 September 2024.
- Minor 1. Download here. Posted 9 August 2024. Due on Gradescope by 11:55PM, 11 August 2024.
Policies
Collaboratation and Plagiarism Policy
- 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 three bullet points) will
have the following consequences: You will receive a 0 in the exam in which the copying is detected.
- Prior to the course withdrawal deadline: All further exams will not be graded. You will be encouraged to withdraw the class. If you do not then you will be assiged a grade as per the policy applied to those caught cheating after the course withdrawal deadline.
- After the course withdrawal deadline: If your score based on previous evaluations is >=30, your score will be reduced to 30 and you will get a D grade. If it is <=20 you will receive an F and if it is between 20 and 30 you will get an E but not allowed to take a remajor.
- This is an
700-level class and a high degree of integrity should be considered a prerequisite. Accordingly, if two students papers are similar, both will get the same penalty irrespective of any claim like "please don't penalize X because I copied from X and not the other way round."
Attendance policy
Any student with less than 75% attendance will receive one letter grade less than the grade based on evaluations. Audit students with less than 75% attendance will receive and Audit Fail grade irrespective of exam scores.
Audit policy
Audit pass will be given at 50%.
Amitabha
Bagchi