Random Walk Sampling - Examples & Techniques for Bounding Mixing Tim
- ACO Student Seminar
- Wednesday, February 18, 2009 - 13:30 for 2 hours
- ISyE Executive Classroom
- Linji Yang – CS, Georgia Tech
In this talk I will give an introduction of the Markov Chain Monte Carlo Method, which uses markov chains to sample interesting combinatorial objects such as proper colorings, independent sets and perfect matchings of a graph. I will introduce methods such as Couplings and Canonical Paths which have been widely used to analyze how many steps Markov Chains needs to go (mixing time) in order to get a sufficiently random combinatorial object. I will also give a brief survey of some recent results in the sampling of colorings.