Variable Length Path Coupling

Thomas P. Hayes; Eric Vigoda

Variable Length Path Coupling

Thomas P. Hayes
, Eric Vigoda

Department of Computer Science and Engineering

The University of Chicago

Research output: Contribution to conference › Paper › peer-review

9 Scopus citations

Abstract

We present a new technique for constructing and analyzing couplings to bound the convergence rate of finite Markov chains. Our main theorem is a generalization of the path coupling theorem of Bubley and Dyer, allowing the defining partial couplings to have length determined by a random stopping time. Unlike the original path coupling theorem, our version can produce multi-step (non-Markovian) couplings. Using our variable length path coupling theorem, we improve the upper bound on the mixing time of the Glauber dynamics for randomly sampling colorings.

Original language	English
Pages	96-103
Number of pages	8
State	Published - 2004
Event	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004

Conference

Conference	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	New Orleans, LA.
Period	01/11/04 → 01/13/04

Cite this

@conference{08d019ef0af241b0beff481f67eda408,

title = "Variable Length Path Coupling",

abstract = "We present a new technique for constructing and analyzing couplings to bound the convergence rate of finite Markov chains. Our main theorem is a generalization of the path coupling theorem of Bubley and Dyer, allowing the defining partial couplings to have length determined by a random stopping time. Unlike the original path coupling theorem, our version can produce multi-step (non-Markovian) couplings. Using our variable length path coupling theorem, we improve the upper bound on the mixing time of the Glauber dynamics for randomly sampling colorings.",

author = "Hayes, \{Thomas P.\} and Eric Vigoda",

year = "2004",

language = "English",

pages = "96--103",

note = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

TY - CONF

T1 - Variable Length Path Coupling

AU - Hayes, Thomas P.

AU - Vigoda, Eric

PY - 2004

Y1 - 2004

N2 - We present a new technique for constructing and analyzing couplings to bound the convergence rate of finite Markov chains. Our main theorem is a generalization of the path coupling theorem of Bubley and Dyer, allowing the defining partial couplings to have length determined by a random stopping time. Unlike the original path coupling theorem, our version can produce multi-step (non-Markovian) couplings. Using our variable length path coupling theorem, we improve the upper bound on the mixing time of the Glauber dynamics for randomly sampling colorings.

AB - We present a new technique for constructing and analyzing couplings to bound the convergence rate of finite Markov chains. Our main theorem is a generalization of the path coupling theorem of Bubley and Dyer, allowing the defining partial couplings to have length determined by a random stopping time. Unlike the original path coupling theorem, our version can produce multi-step (non-Markovian) couplings. Using our variable length path coupling theorem, we improve the upper bound on the mixing time of the Glauber dynamics for randomly sampling colorings.

UR - https://www.scopus.com/pages/publications/1842525774

M3 - Paper

AN - SCOPUS:1842525774

SP - 96

EP - 103

T2 - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 11 January 2004 through 13 January 2004

ER -

Variable Length Path Coupling

Abstract

Conference

Other files and links

Fingerprint

Cite this