COL727: Rapid Mixing in Markov Chains

I semester: 2024-25

Amitabha Bagchi

Class Timings: Tu Fr 3:30PM.
Room: TBA.

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.

Evaluation

There will be 4 take-home exams, each carrying 25% weight.

Exams

TBA

Policies

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 700-level class and a high degree of integrity should be considered a prerequisite.
Attendance policy. Any student with less than 75% attendance will not be allowed to take the 4th take home exam.
Audit policy. Audit pass will be given at 50%.

Amitabha Bagchi