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, and sometimes brief sketches of proofs. Motivation, intuition, and complete 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 / Gibbs sampling.
4. Convergence of Markov Chains
   1. Reversible Chains: $\ell^2$ convergence, spectral gap.
   2. Mixing times: TV Convergence, relaxation time, time averages.
   3. Coupling: Markovian couplings, applications to the random walks on the cycle, torus and binary hypercube.
5. Simulated Annealing: Simulated annealing, travelling salesman, substitution ciphers.
6. Simulated and Parallel Tempering: Mixing bottlenecks, simulated tempering, parallel tempering.
7. Extra topics
   1. Recurrence and transience