Name
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 multistep (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. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 A preliminary version of this paper appeared in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 103–110. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1002/rsa.v31:3 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
preliminary version,glauber dynamic,fifteenth annual acm-siam symposium,variable length path coupling,discrete algorithms,defining partial coupling,original path coupling theorem,path coupling theorem,inc. random struct,main theorem,mixing time,upper bound,markov chain monte carlo,stopping time,random sampling,convergence rate,markov chain | Discrete mathematics,Glauber,Markov chain mixing time,Combinatorics,Coupling,Markov chain Monte Carlo,Upper and lower bounds,Markov chain,Rate of convergence,Stopping time,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 3 | 1042-9832 |
ISBN | Citations | PageRank |
0-89871-558-X | 8 | 0.64 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas P. Hayes | 1 | 659 | 54.21 |
| Eric Vigoda | 2 | 747 | 76.55 |