Slow Mixing of Markov Chains Using Fault Lines and Fat Contours

摘要

We show that local dynamics require exponential time for two sampling problems motivated by statistical physics: independent sets on the triangular lattice (the hard-core lattice gas model) and weighted even orientations of the two-dimensional 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. Unfortunately, establishing slow mixing for these models has been a challenge, as standard contour arguments typically used to show that a chain has small conductance do not seem to apply. We modify this approach by introducing the notion of fat contours that can have nontrivial area, and use these to establish slow mixing of local chains defined for these models.