Abstract
The canonical paths argument is an important technique to prove the rapid mixing property of Markov chains. It plays an important role in the analysis of Markov chains for sampling matchings, Jerrum-Sinclair's chain for Ising model and the Markov chain for permanent. However, there are much fewer success examples comparing to coupling, another technique for bounding mixing time. The main reason is that there is no systematic approach or general recipe to design canonical paths.
Recently, McQuillan gave a nice generalization of the Glauber dynamics for sampling matchings in the framework of Holant problems. Based on his exploration, we develop a general theory to design canonical paths for Markov chains: We reduce the task of designing canonical paths to solving a set of linear equations, which can be easily done even by hand.
In this talk, I will first introduce McQuillan's generalization and our new characterization of the canonical paths. Then I will interpret many known success examples of canonical paths arguments in our new theory. Finally, I will show how to obtain fully polynomial-time randomized approximation schemes (FPRAS) for counting the number of b-matching with b<=7 and b-edge-cover with b<=2 using our new approach, which are natural generalizations of counting matchings and edge covers in graphs.
This is a joint work with Lingxiao Huang and Pinyan Lu.