Premium
Coupling vs. conductance for the Jerrum–Sinclair chain *
Author(s) -
Anil Kumar V.S.,
Ramesh H.
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200101)18:1<1::aid-rsa1>3.0.co;2-7
Subject(s) - markov chain , bipartite graph , conductance , mathematics , coupling (piping) , combinatorics , markov chain mixing time , discrete mathematics , statistical physics , chain (unit) , mixing (physics) , graph , quantum mechanics , markov model , physics , variable order markov model , statistics , materials science , metallurgy
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. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 1–17, 2001