The main technique used in algorithm design for approximatingheart of the method is the study of the convergence (mixing) rates ofparticular Markov chains of interest. In this paper we illustrate a newapproach to the coupling technique, which we call path coupling, forbounding mixing rates. Previous applications of coupling have requireddetailed insights into the combinatorics of the problem at hand, andthis complexity can make the technique extremely difficult to applysuccessfully. Path coupling helps to minimize the combinatorialdifficulty and in all cases provides simpler convergence proofs thandoes the standard coupling method. However the true power of the methodis that the simplification obtained may allow coupling proofs which werepreviously unknown, or provide significantly better bounds than thoseobtained using the standard method. We apply the path coupling method toseveral hard combinatorial problems, obtaining new or improved results.We examine combinatorial problems such as graph colouring and TWICE-SAT,and problems from statistical physics, such as the antiferromagneticPotts model and the hard-core lattice gas model. In each case we provideeither a proof of rapid mixing where none was known previously, orsubstantial simplification of existing proofs with consequent gains inthe performance of the resulting algorithms
展开▼
