Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Slow Mixing of Markov Chains Using Fault Lines and Fat Contours
| |
|
Slow Mixing of Markov Chains Using Fault Lines and Fat Contours
Sam Greenberg5 and Dana Randall6
| (5) |
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, |
| (6) |
College of Computing, Georgia Institute of Technology, Atlanta, GA 30332-0280, |
Abstract
We show that local dynamics require exponential time for two sampling problems: independent sets on the triangular lattice
(the hard-core lattice gas model) and weighted even orientations of the Cartesian lattice (the 8-vertex model). For each problem,
there is a parameter λ known as the fugacity such that local Markov chains are expected to be fast when λ is small and slow when λ is large. However, establishing slow mixing for these models has been a challenge because standard contour arguments typically
used to show that a chain has small conductance do not seem sufficient. We modify this approach by introducing the notion
of fat contours that can have nontrivial d-dimensional volume and use these to establish slow mixing of local chains defined for these models.
Supported in part by NSF grants CCR-0515105 and DMS-0505505.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|