Coupling vs. conductance for the Jerrum-Sinclair chain

Anil Kumar, V. S. ; Ramesh, H. (2001) Coupling vs. conductance for the Jerrum-Sinclair chain Random Structures and Algorithms, 18 (1). pp. 1-17. ISSN 1042-9832

Full text not available from this repository.

Official URL:

Related URL:<1::AID-RSA1>3.0.CO;2-7


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.

Item Type:Article
Source:Copyright of this article belongs to John Wiley & Sons, Inc.
ID Code:102373
Deposited On:09 Mar 2018 11:24
Last Modified:09 Mar 2018 11:24

Repository Staff Only: item control page