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

Logistical Info

  • Course website: https://www.math.cmu.edu/~gautam/c/2025-326

  • Staff: Gautam Iyer (Instructor), SJ Son (TA), Jerick Shi (TA)

  • Join the Discussion board and mailing on the website.

  • Please use the discussion board for questions / clarifications

    • Avoid using email if possible.

  • Office hours will be posted shortly.

Homework

  • Due every week on Wed, 1h before class starts.

  • OK to collaborate, use online resources, AI, provided

    • You write up solutions independently,
    • and you only turn in solutions you understand,

  • A good portion of your grade is closed book in class exams.

    • Not understanding the homework = bad performance on the exams

  • Worth 30% of your grade

Exams

  • Midterm 1: Wed 5th week (Sep 24), closed book, in class.

  • Midterm 2: Week of Nov 3rd (10th week), format TBD

  • Final:

    • Will have a closed book, in class component

    • Will also have a project / take home component

    • In class component at the time scheduled by the registrar.

Grading

  • Each midterm will count as 20%.

  • The final will count as 30%.

  • Homework will count as 30% of your grade.

  • To pass the class, you must pass the in class component of the exams

    • This rule is mainly to check you understand your own homework solutions

Course Outline

  1. Markov chains
  2. Sampling
  3. Markov Chain Monte Carlo
  4. Applications

Example: Substitution Ciphers

  • Alice and Bob agree on a permutation of the alphabet (e.g. $A \mapsto K$, $B \mapsto Z$, etc.)

  • Alice sends Bob a coded message:

    LAVLCRQPTVIWLRVTKQCLCRQLMCLETDEJCLARQLDVKEYSLMLREGQLCQTFVKLRQEPFLRMKLKQYAMVYLRQPLHYFQPLEYJLVARQPLYEK
QSLMYLRMCLQJQCLCRQLQITMBCQCLEYFLBPQFVKMYEAQCLARQLDRVTQLVNLRQPLCQUSLMALDECLYVALAREALRQLNQTALEYJLQKVAM
VYLEWMYLAVLTVGQLNVPLMPQYQLEFTQPSLETTLQKVAMVYCLEYFLAREALVYQLBEPAMIHTEPTJLDQPQLEXRVPPQYALAVLRMCLIVTFLB
PQIMCQLXHALEFKMPEXTJLXETEYIQFLKMYFSLRQLDECLMLAEWQLMALARQLKVCALBQPNQIALPQECVYMYOLEYFLVXCQPGMYOLKEIRMY

  • Brute force cracking requires trying $30! \approx 10^{29}$ combinations.

    • Takes $10^{19}$ seconds at 10 billion combinations per second

    • Age of the universe is roughly $10^{19}$ seconds.

  • If the message is a few paragraphs of English text, we can crack this in seconds.

    • Will be on homework later; but try it now for fun.

How are randomly packed disks arranged?

Left: Packing density 0.5. Right: Packing density 0.72

  • Randomly pack a fixed number of non-overlapping identical disks in a box.

  • When the packing density becomes large, the arrangement is nearly hexagonal.

  • How do you check this numerically?

How are randomly packed disks arranged?

  • Need a way to practically sample from all possible (valid) disk arrangements

  • The space of all valid configurations is a bounded open set in $\R^{2N}$

  • Need to sample the uniform measure on this set.

  • If $N \geq 20$ this is already hard by traditional methods; we want $N \approx 100$–$10^6$

  • The Metropolis Hastings algorithm was developed to study this.

    • It’s now widely used in many other applications, which we will study