Slow Mixing of Markov Chains Using Fault Lines and Fat Contours

摘要

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.