Details

Autor(en) / Beteiligte

• Anil Kumar, V.S.
• Ramesh, H.

Titel

Coupling vs. conductance for the Jerrum-Sinclair chain

Ist Teil von

• Random structures & algorithms, 2001-01, Vol.18 (1), p.1-17

Ort / Verlag

New York: John Wiley & Sons, Inc

Erscheinungsjahr

2001

Link zum Volltext

Quelle

Wiley Online Library

Beschreibungen/Notizen

• 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