# Markov Chains

### Spring 2013

#### T / Th, 4:35 - 5:55 pm

Instructor

Will Perkins

wperkins3@math.gatech.edu

Office: Skiles 017

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:
1. Markov Chain
2. Discrete / Continuous, time and state space
3. Homogeneous MC
4. Transition Matrix
5. Chapman-Kolmogorov Eqs
6. Irreducible
7. Periodic
8. Transient, Positive Recurrent, Null Recurrent and how to prove
9. Decomposition Theorem
10. Closed States, Intercommunicating States
11. Stationary Distribution
12. Detailed Balance, Reversibility
13. Convergence Theorem
14. Total Variation Distance
15. Mixing Time
16. Bounds on Mixing Times
17. Metropolis Algorithm
18. Perron-Frobenius
19. Eigenvalue Bound on TV distance from Stationarity
• Sample Questions:
1. 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.
2. Bound the mixing time of a random walk on two complete graphs of size n joined by a single edge
3. 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?