Coupling vs. conductance for the Jerrum-Sinclair chain

We address the following question: is the causal coupling method as strong as the conductance method in showing rapid mixing of Markov chains? A causa l coupling is a coupling which uses only past and present information, but not information about the future. We answer the above question in the negat ive by showing that there exists a bipartite graph G such that any causal c oupling argument on the Jerrum-Sinclair Markov chain for sampling almost un iformly from the set of perfect and near perfect matchings of G must necess arily take time exponential in the number of vertices in G. In contrast, th e above Markov chain on G has been shown to mix in polynomial time using co nductance arguments. (C) 2001 John Wiley & Sons, Inc.