Topics

- Sections: 6.1 - 6.6, 6.14
- Notes: Markov Chains, Stationary Distributions of Markov Chains, MCMC and Mixing Times, Eigenvalues and Markov Chains
- Homework Problems: HW 7
- Definitions and Theorems:
- Markov Chain
- Discrete / Continuous, time and state space
- Homogeneous MC
- Transition Matrix
- Chapman-Kolmogorov Eqs
- Irreducible
- Periodic
- Transient, Positive Recurrent, Null Recurrent and how to prove
- Decomposition Theorem
- Closed States, Intercommunicating States
- Stationary Distribution
- Detailed Balance, Reversibility
- Convergence Theorem
- Total Variation Distance
- Mixing Time
- Bounds on Mixing Times
- Metropolis Algorithm
- Perron-Frobenius
- Eigenvalue Bound on TV distance from Stationarity

- Sample Questions:
- Let G be the graph of two cycles of length n joined by a single edge. Give bounds on the mixing time of the random walk on G.
- Bound the mixing time of a random walk on two complete graphs of size n joined by a single edge
- Consider a MC on two states that moves to the other state with probability .99 and remains where it is with probability .01. How many steps until the chain is at distance 1/4 from stationary?