Path coupling without contraction (Q2457299)

A coupling for a \(\Omega \)-valued Markov chain is simply a joint evolution of two copies of the chain. The usual approach is to define an appropriate metric on \(\Omega \;\)and to show that each step of a suitable coupling produces a contraction in distance between any pair of states. The difficulty with applying this method, however, is that good couplings may not be easy to find, and can be difficult to analyze directly. The evolution of the coupling must be defined and analyzed for all pairs of states in the chain. Path coupling is a technique for simplifying the analysis of a coupling of a Markov chain. Rather than defining and analyzing the coupling on every pair in \(\Omega \times \Omega \), analysis is done on a smaller set \(S\subseteq \Omega \times \Omega \). If the coefficient of contraction \(\beta \) is strictly less than one, no further analysis is needed in order to show rapid mixing. However, if \(\beta =1\) then analysis (of the variance) is still required for all pairs in \(\Omega \times \Omega \) . The authors present a new approach which shows rapid mixing in the case \( \beta =1\) with a further condition which only needs to be checked for pairs in \(S\), greatly simplifying the work involved. They also present a technique applicable when \(\beta =1\) and their condition is not met.