标题： 平均上稀疏图上的吉布斯采样的快速混合 显示英文标题

标题： Rapid Mixing of Gibbs Sampling on Graphs that are Sparse on Average

摘要： 在本工作中，我们证明对于每个 $d < \infty$以及定义在 $G(n,d/n)$上的伊辛模型，存在一个 $\beta_d > 0$，使得对于所有 $\beta < \beta_d$，当 $n \to \infty$时，动力学在 $G(n,d/n)$上的混合时间是 $n$的多项式。 我们的结果是首次在$G(n,d/n)$上对于$d > 1$的自然模型证明的多项式时间混合结果，其中模型的参数不依赖于$n$。 它们还提供了一个罕见的例子，可以在实际混合时间比$n \polylog(n)$更慢的情况下证明吉布斯采样器的多项式时间混合。 我们的证明以新颖的方式利用了 Erdős-Rényi 随机图的局部树状结构、比较和块动力学论证以及 Weitz 的最新结果。 我们的结果扩展到更广泛的图族，这些图在某种平均意义上是稀疏的，并且适用于更广泛的相互作用。 特别是，它们适用于任何图，其中图的每个顶点$v$的半径为$O(\log n)$的邻域$N(v)$中的诱导子图是树加上最多$O(\log n)$条边，并且对于$N(v)$中的每个简单路径，路径上顶点度数之和为$O(\log n)$。 此外，我们的结果也适用于任意外部场情况，并提供了在这种情况下对伊辛分布进行采样的第一个FPRAS。 我们最后提出了一种非马尔可夫链算法来对分布进行采样，该算法在更广泛的参数范围内有效。 特别是，对于$G(n,d/n)$，它适用于所有外部场，以及$\beta < \beta_d$，其中$d \tanh(\beta_d) = 1$是伊辛模型在$G(n,d/n)$上相关性衰减的临界点。 显示英文摘要

摘要： In this work we show that for every $d < \infty$ and the Ising model defined on $G(n,d/n)$, there exists a $\beta_d > 0$, such that for all $\beta < \beta_d$ with probability going to 1 as $n \to \infty$, the mixing time of the dynamics on $G(n,d/n)$ is polynomial in $n$. Our results are the first polynomial time mixing results proven for a natural model on $G(n,d/n)$ for $d > 1$ where the parameters of the model do not depend on $n$. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than $n \polylog(n)$. Our proof exploits in novel ways the local treelike structure of Erd\H{o}s-R\'enyi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex $v$ of the graph has a neighborhood $N(v)$ of radius $O(\log n)$ in which the induced sub-graph is a tree union at most $O(\log n)$ edges and where for each simple path in $N(v)$ the sum of the vertex degrees along the path is $O(\log n)$. Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for $G(n,d/n)$ it applies for all external fields and $\beta < \beta_d$, where $d \tanh(\beta_d) = 1$ is the critical point for decay of correlation for the Ising model on $G(n,d/n)$.