21-326 Markov Chains: Theory, Simulation and Applications

9 units, Carnegie Mellon University

This course is a natural sequel to 21-325 (Probability) covering Markov Chains and several applications. 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), and analyzes several applications that arise in CS (counting matchings, pagerank, graph coloring), statistical physics (Ising model, hard core model) and optimization (traveling salesman). While several applications will be implemented on a computer (using numerical Python), students will be given starter code and only be asked to implement key mathematical steps of the algorithm. (Three 50 minute lectures)

Prerequisites: (15-112 or 02-120) and (21-325 or 15-259) and (21-240 or 21-241 or 21-242)

Offered: Spring 2027, Fall 2025

Courseweave needs JavaScript to show sections, workloads and planning tools.