论文标题
通过收缩快速混合Glauber动力学至唯一性
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
论文作者
论文摘要
对于一般抗铁磁2旋转系统，包括铁杆模型和抗磁磁性ISING模型，当在Li等人的独特区域中，无限的定期树在最大程度上$Δ$的分区功能上有一个$ \ mathsf {fptas} $。 （2013）。此外，在树非唯一区域中，Sly（2010）表明，除非$ \ Mathsf {np} = \ Mathsf {rp} $，否则没有$ \ mathsf {fpras} $来估计分区功能。算法结果来自Weitz（2006）引起的相关衰减方法或Barvinok（2016）开发的多项式插值方法。但是，对于常数$δ$，运行时间仅是多项式。对于铁杆模型，Anari等人的最新工作。 （2020）建立了简单的单位马尔可夫链的快速混合，称为树独特区域中的Glauber动力学。我们的工作通过考虑固定顶点$ v $对其他顶点的总成对影响来简化他们对Glauber动态的分析，而不是对$ V $的总影响，从而将其工作扩展到所有2型旋转模型并改善混合时间。 更重要的是，我们的证明将三种不同的算法方法联系在一起：我们表明，具有适当潜在功能的树递归的收缩，这是建立Weitz相关衰减方法的主要技术，而Barvinok的多项式插值方法也建立了Glauber Dynamics的迅速混合。我们强调，这种连接适用于所有2旋式模型（抗铁磁和铁磁），以及相关衰减或多项式插值的现有证据，立即暗示着Glauber动力学的快速混合。我们的证明利用图形分区功能将Weitz自我避开树木的函数划分为分析顶点影响的新工具。
For general antiferromagnetic 2-spin systems, including the hardcore model and the antiferromagnetic Ising model, there is an $\mathsf{FPTAS}$ for the partition function on graphs of maximum degree $Δ$ when the infinite regular tree lies in the uniqueness region by Li et al. (2013). Moreover, in the tree non-uniqueness region, Sly (2010) showed that there is no $\mathsf{FPRAS}$ to estimate the partition function unless $\mathsf{NP}=\mathsf{RP}$. The algorithmic results follow from the correlation decay approach due to Weitz (2006) or the polynomial interpolation approach developed by Barvinok (2016). However the running time is only polynomial for constant $Δ$. For the hardcore model, recent work of Anari et al. (2020) establishes rapid mixing of the simple single-site Markov chain known as the Glauber dynamics in the tree uniqueness region. Our work simplifies their analysis of the Glauber dynamics by considering the total pairwise influence of a fixed vertex $v$ on other vertices, as opposed to the total influence on $v$, thereby extending their work to all 2-spin models and improving the mixing time. More importantly our proof ties together the three disparate algorithmic approaches: we show that contraction of the tree recursions with a suitable potential function, which is the primary technique for establishing efficiency of Weitz's correlation decay approach and Barvinok's polynomial interpolation approach, also establishes rapid mixing of the Glauber dynamics. We emphasize that this connection holds for all 2-spin models (both antiferromagnetic and ferromagnetic), and existing proofs for correlation decay or polynomial interpolation immediately imply rapid mixing of Glauber dynamics. Our proof utilizes that the graph partition function divides that of Weitz's self-avoiding walk trees, leading to new tools for analyzing influence of vertices.
