Random Walk Sampling - Examples & Techniques for Bounding Mixing Tim

ACO Student Seminar
Wednesday, February 18, 2009 - 13:30
2 hours
ISyE Executive Classroom
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.