| Coupling vs. conductance for the Jerrum-Sinclair chain (2001) | |||||||||||||
Abstract | |||||||||||||
| We address the following question: is the causal coupling method as strong as the conductance method in showing rapid mixing of Markov chains? A causal coupling is a coupling which uses only past and present information, but not information about the future. We answer the above question in the negative by showing that there exists a bipartite graph G such that any causal coupling argument on the Jerrum–Sinclair Markov chain for sampling almost uniformly from the set of perfect and near perfect matchings of G must necessarily take time exponential in the number of vertices in G. In contrast, the above Markov chain on G has been shown to mix in polynomial time using conductance arguments. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||