Dana Randall, Georgia Institute of Technology
Cupid's Monte Carlo: matchings, couplings and other
tales of mixing
Markov chain Monte Carlo techniques are used extensively in practice to study properties of large combinatorial sets. From a rigorous standpoint, the two main challenges lie in developing techniques to analyze the mixing times, or convergence rates, of Markov chains and designing fast Monte Carlo algorithms to address specific applications. In this talk, we will outline how coupling and related methods can be used to bound mixing times. In addition, we will demonstrate how simulated tempering can be used to greatly speed up slow chains. Applications will include the Ising model and perfect matchings.