21-326: Markov Chains: Theory, Simulation and Applications

Fall 2025

Course Information

Office Hours and Discussion Board

Time Place Person
Mon 1:00--3:00 WEH 6203 SJ Son
Tue 1:30--3:20 WEH 6215 Jerick Shi
Fri 1:15--3:00 WEH 8115 Gautam Iyer

Use the discussion board for all questions, and join to the mailing list to receive announcements.

Homework

Homework is due every Wednesday at 10:00 AM on Gradescope, one hour before class starts. (Use this invite code if you’re not signed up). Please read the late homework policy

Handouts

Exams Schedule

  • Midterm 1: Fri, Sep 26 (5th week), closed book, in class.
  • Midterm 2: Week of Nov 3rd, format to be decided.
  • The final will have both a closed book in class component, and a take home component. The in class component will be at the time announced by the registrar here. Be aware of their schedule before making your travel plans.

Grading

Your scores on exams and homework will each be converted to a grade point with A=4.0, B=3.0, etc. on a scale that will be announced after each exam. The grade points will be averaged with the following weights:

  • Each midterm will count as 20%.
  • The final will count as 30%.
  • Homework will count as 30% of your grade.

In order to pass the class you must the closed book in class portion of the exams. Precisely, your average grade point on the closed book in class portion of the exams, and with weights proportional to those listed above, must be a passing grade point (at least 1.0). The in class exams will be designed so that students who have done well on the homework will be able to pass the exams, provided they understand their own solutions to the homework.

Course description.

Markov Chains arise in several situations that most of us use in everyday life (e.g. next word prediction on our smartphone keyboards, and ranking results in internet searches). This course covers the basics Markov chains in a mathematically rigorous way, the basics of sampling, and MCMC (Markov Chain Monte Carlo). We will study (theoretically, and/or numerically) a few examples that arise in CS (counting matchings, pagerank, graph coloring), statistical physics (Ising model, hard core model) and optimization (traveling salesman). The numerical portions of this course will be done using Python (using NumPy and SciPy). The focus will be on the mathematical aspects, and so students will typically be given starter code and only be asked to implement key mathematical steps of the algorithm.

Tentative Syllabus

Topics covered

  1. Markov chains: basic notions, stationary distribution, mixing times, techniques to estimate mixing times.
  2. Sampling: random number generation, importance sampling, rejection sampling.
  3. Markov Chain Monte Carlo: Metropolis Hastings, Gibbs sampling, Tempering, Sequential Monte Carlo.
  4. Applications: Page rank, Monte Carlo integration, hard core model, traveling salesman, Ising model, graph coloring, gerrymandering.

A few applications will be implemented on a computer using scientific / numerical Python. (No prior knowledge of Python is required, but some experience with coding is helpful.)

Learning Objectives

  1. Understand the theoretical foundations of Markov Chains, and be proficient with the proofs of basic results in the field.
  2. Understand the problems involved with sampling, and the fundamental techniques used to address them
  3. Study MCMC and several applications.
  4. Understand the basics of simulation, and code a few applications using numerical Python.

Pre-requisites

  • A rigorous and through first course on Probability (e.g. 21-325 or 21-721).
  • Linear algebra (e.g. 21-240, 21-241 or 21-242).
  • Some familiarity with coding (not necessarily Python)

References

Class Policies

Lectures

  • If you must sleep, don’t snore!
  • Be courteous when you use mobile devices

Homework

  • The primary purpose of homework is to help you understand the material!
    • You may collaborate, use AI/online resources, etc. freely, as long as you learn from the solutions you turn in, and you write up the solutions yourself independently.
    • Turning in solutions you don’t understand will be treated as a violation of academic integrity.
    • A significant portion of your grade will involve exams where you do not have access to the internet, friends and AI. If you haven’t fully understood the homework, you will most likely do very poorly on the exams.
    • I recommend starting the homework early. Most students will not be able to do the homework in one evening.
  • All homework must be scanned and turned in via Gradescope. (Everyone who was registered for this class on day 1 was automatically added to Gradescope. If you joined later, use this invite code to add yourself.)
  • Please take good quality scans; homework that’s too hard to read won’t be graded. I recommend using a good scanning app that adjusts the contrast of your images for readability. (I’ve had good luck with Adobe Scan, and Google Drive.)
  • In order to ensure academic integrity is maintained, we may randomly quiz some students about their homework solutions.
  • Nearly perfect student solutions may be scanned and hosted here, with your identifying information removed. If you don’t want any part of your solutions used, please make a note of it in the margin of your assignment.

Exams

  • For closed book exams, no calculators, computational aids, or internet enabled devices are allowed.
  • The final time will be announced by the registrar here. Be aware of their schedule before making your travel plans.

Academic Integrity

  • All students are expected to follow the academic integrity standards outlined here.
  • There will be zero tolerance for academic integrity violations, and any violation will result in an automatic R. Examples of academic integrity violations include (but are not limited to):
    • Not writing up solutions independently and/or plagiarizing solutions.
    • Turning in solutions you do not understand.
    • Receiving assistance from another person during an exam.
    • Providing assistance to another person taking an exam.
  • All academic integrity violations will further be reported to the university, and the university may chose to impose an additional penalty.

Accommodations for Students with Disabilities

If you have a disability and have an accommodations letter from the Disability Resources office, I encourage you to discuss your accommodations and needs with me as early in the semester as possible. I will work with you to ensure that accommodations are provided as appropriate. If you suspect that you may have a disability and would benefit from accommodations but are not yet registered with the Office of Disability Resources, I encourage you to contact them at access@andrew.cmu.edu.

Student Wellness

As a student, you may experience a range of challenges that can interfere with learning, such as strained relationships, increased anxiety, substance use, feeling down, difficulty concentrating and/or lack of motivation. These mental health concerns or stressful events may diminish your academic performance and/or reduce your ability to participate in daily activities. CMU services are available, and treatment does work. You can learn more about confidential mental health services available on campus here. Support is always available (24/7) from Counseling and Psychological Services: 412-268-2922.

Faculty Course Evaluations

At the end of the semester, you will be asked to fill out faculty course evaluations. Please fill these in promptly, I value your feedback. As incentive, if over 75% of you have filled out evaluations on the last day of class, then I will release your grades as soon as they are available. If not, I will release your grades at the very end of the grading period.