24.07.2006

In this paper we examine the importance of the choice of metric inpath coupling, and its relationship to stopping timeanalysis. We give strong evidence that stopping time analysis is nomore powerful than standard path coupling. In particular, we prove astronger theorem for path coupling with stopping times, using ametric which allows us to analyse a one-step path coupling. Thisapproach provides insight for the design of better metrics forspecific problems. We give illustrative applications to hypergraphindependent sets and SAT instances, hypergraph colourings andcolourings of bipartite graphs, obtaining improved results for allthese problems.