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

标题： 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)$更慢。 我们的证明以新颖的方式利用了埃德罗斯-雷尼随机图的局部树状结构、比较和块动力学论证以及 Weitz 的最新结果。 我们的结果扩展到更一般的图族，这些图在某种平均意义上是稀疏的，并且扩展到更一般的相互作用。 特别是，它们适用于任何图，其中图的每个顶点$v$的邻域$N(v)$在半径$O(\log n)$内，其中的诱导子图是树加上最多$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)$.