CMSC 37101
Markov Chain Monte Carlo MethodsPrerequisites: Consent of instructor.
Catalog Description: This course covers the Markov chain Monte Carlo method for enumeration and sampling problems. Analytic tools for the asymptotic analysis of Markov chains, including probabilistic, combinatorial, and geometric tools are discussed. We study these techniques in the context of prominent results in the field: estimating the volume of a convex body and computing the permanent of a matrix. Other topics include Markov chains, complexity class #P, exact sampling techniques, path coupling, stopping times, and connections to statistical physics.
Long Description: This course covers the Markov chain Monte Carlo method for enumeration and sampling problems. There has been tremendous progress in this field over the past decade, stemming from new analytic tools for the asymptotic analysis of Markov chains. These tools primarily fall into three varieties: probabilistic (via coupling), combinatorial (via multi-commodity flows), and geometric (via isoperimetric inequalities).
We will study these techniques in the context of the prominent results of the field: estimating the volume of a convex body and computing the permanent of a matrix. Some other topics (likely) to be covered: Markov chains, complexity class #P, exact sampling techniqus, path coupling, stopping times, and connections to statistical physics.
Instructors: Eric VigodaQuarter offered: Autumn
Last Verified by Sharon Salveter on 8 April, 2003.