Coupling vs. conductance for the Jerrum–Sinclair chain

✍ Scribed by V.S. Anil Kumar; H. Ramesh

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 149 KB
• Volume: 18
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/1098-2418(200101)18:1<1::aid-rsa1>3.0.co;2-7

✦ Synopsis

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.