Slow Mixing of Markov Chains Using Fault Lines and?Fat Contours

详细信息    查看全文

• 作者：Sam Greenberg and Dana Randall
• 关键词：Markov chain ; Glauber dynamics ; Mixing time ; Independent sets ; Triangular lattice ; 8 ; vertex model ; Slow mixing
• 刊名：Algorithmica
• 出版年：2010
• 出版时间：December 2010
• 年：2010
• 卷：58
• 期：4
• 页码：911-927
• 全文大小：509.8 KB

文摘

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.