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.
My Menu
Saved Items

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)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.114 • Server: mpweb19
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)