Markov Chains

MATH 6221

Spring 2013

Skiles 169

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


Will Perkins

Office: Skiles 017

  • 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?