Sampling from the $q$-state ferromagnetic Potts model is a fundamental question in statistical physics, probability theory, and theoretical computer science. On general graphs, this problem is computationally hard, and this hardness holds at arbitrarily low temperatures. At the same time, in recent years, there has been significant progress showing the existence of low-temperature sampling algorithms in various specific families of graphs. Our aim in this paper is to understand the minimal structural properties of general graphs that enable polynomial-time sampling from the $q$-state ferromagnetic Potts model at low temperatures. We study this problem from the perspective of the widely-used Swendsen--Wang dynamics and the closely related random-cluster dynamics. Our results demonstrate that the key graph property behind fast or slow convergence time for these dynamics is whether the independent edge-percolation on the graph admits a strongly supercritical phase. By this, we mean that at large $p<1$, it has a unique giant component of linear size, and the complement of that giant component is comprised of only small components. Specifically, we prove that such a condition implies fast mixing of the Swendsen--Wang and random-cluster dynamics on two general families of bounded-degree graphs: (a) graphs of at most stretched-exponential volume growth and (b) locally treelike graphs. In the other direction, we show that, even among graphs in those families, these Markov chains can converge exponentially slowly at arbitrarily low temperatures if the edge-percolation condition does not hold. In the process, we develop new tools for the analysis of non-local Markov chains, including a framework to bound the speed of disagreement propagation in the presence of long-range correlations, and an understanding of spatial mixing properties on trees with random boundary conditions.


翻译:抽取 $q$ 状态铁磁 Potts 模型样本是统计物理学、概率论和理论计算机研究的基础问题。一般来说,在任意低温下,这个问题在普通图上是计算上困难的。与此同时,近年来,有关于在特殊的图族上存在低温采样算法的重要进展。本文旨在从广泛采用的 Swendsen-Wang 动力学(及其紧密相关的随机群集动力学)的角度,理解一般图的最小结构特性,以实现多项式时间采样 $q$ 状态铁磁 Potts 模型在低温下的问题。我们研究这个问题,关注广义图的独立边渗流的关键图形特性,判断这些动态的收敛速度是快还是慢的。其中,关键的问题是边渗透是否存在强超临界相。我们指的是在大的 $p<1$ 时,存在一个线性大小的唯一巨型组件,其补集由少量的小组件组成的情况。具体而言,我们证明这样的条件意味着在有界度的图的两个一般性族中,Swendsen-Wang 与随机群集动力学的快速混合:(a) 最多伸展指数增长的图和(b) 本地类树状图。在另一方面,即使在这些族中的图中,如果边渗透条件不成立,则随机链在任意低温下也可能以指数速度缓慢收敛。在这个过程中,我们开发了非局部马尔科夫链分析的新工具,包括一个框架来限制在存在长程相关性的情况下不一致传播速度,以及了解随机边界条件的树上的空间混合性质。

0
下载
关闭预览

相关内容

机器学习损失函数概述,Loss Functions in Machine Learning
专知会员服务
82+阅读 · 2022年3月19日
【CVPR2022】用于全身图像生成的 InsetGAN
专知会员服务
25+阅读 · 2022年3月17日
【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月24日
Arxiv
0+阅读 · 2023年5月24日
VIP会员
相关VIP内容
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员