Analyzing Glauber dynamics by comparison of Markov chains

Abstract

A popular technique for studying random properties of a combinatorial set is to design a Markov chain Monte Carlo algorithm. For many problems there are natural Markov chains connecting the set of allowable configurations which are based on local moves, or “Glauber dynamics.” Typically these single-site update algorithms are difficult to analyze, so often the Markov chain is modified to update several sites simultaneously. Recently there has been progress in analyzing these more complicated algorithms for several important combinatorial problems. In this work we use the comparison technique of Diaconis and Saloff-Coste to show that several of the natural single-point update algorithms are efficient. The strategy is to relate the mixing rate of these algorithms to the corresponding nonlocal algorithms which have already been analyzed. This allows us to give polynomial time bounds for single-point update algorithms for problems such as generating planar tilings and random triangulations of convex polygons. We also survey several other comparison techniques, along with specific applications, which have been used in the context of estimating mixing rates of Markov chains.