Brief lecture notes

These are the notes for 21-326: Markov Chains: Theory, Simulation and Applications in Fall 2025. These notes only list statements of important results covered in lectures. Motivation, intuition, and proofs will be done in class, and will not be on these notes.

1. Introduction.
2. Markov Chains
   1. Introduction and Examples: Definitions, Examples (Page Rank, Gamblers ruin), Hitting times, Dirichlet and Poisson problems.
   2. The Stationary Distribution: Existence, uniqueness and convergence
3. Introduction to Sampling
   1. Two motivating examples: Disk packing, Ising Model
   2. Basic Sampling Algorithms: Random number generation, Transformation methods, Rejection sampling.
   3. Monte Carlo Approximation: Monte Carlo Method, Importance Sampling, Integration
   4. Markov Chain Monte Carlo: Metropolis–Hastings, Reversibility, Glauber Dynamics
4. Convergence of Markov Chains
   1. Reversible Chains: $\ell^2$ convergence, spectral gap, relaxation time.
   2. Mixing times
   3. Coupling
5. Simulated and Parallel Tempering
6. Extra topics
   1. Recurrence and transience
   2. Simulated Annealing