On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n, d/n)
On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n, d/n)
复制标题
DOI：
10.48550/arxiv.2302.06172
复制
发表时间：
2023-02
影响因子：
6.2
通讯作者：
Charilaos Efthymiou;Weiming Feng
中科院分区：
文献类型：
--
作者：
Charilaos Efthymiou;Weiming Feng
研究了随机图G（n，d/n）上逸度Hard-core模型的单点Glauber动力学.我们证明了对于随机图$G（n，d/n）$和逸度$\lambda<\frac{d^d}{（d-1）^{d+1}}$，Glauber动力学的混合时间为$n^{1 + O（1/\log \log n）}$.我们的结果改进了最近的优雅算法[Bezakova，Galanis，Goldberg Stefankovic; ICALP'22]。该算法有一个基于MCMC的采样算法，但它不是Glauber动力学。我们这里的算法更简单，因为我们使用经典的Glauber动力学。此外，我们证明的混合时间的界限比Bezakova等人的论文更小，因此我们的算法也更快。我们证明中的主要挑战是处理度无界的顶点。我们提供了更强的结果，通过分支值的谱独立性，并表明我们的吉布斯分布满足近似张量化的熵。我们猜想，我们在这里的界限是最佳的$G（n，d/n）$。作为对Hardcore模型分析的推论，我们还得到了G（n，d/n）上Monomer-dimer模型Glauber动力学混合时间的界。我们得到的这个模型的边界比我们得到的硬核模型的边界稍好一些
We study the single-site Glauber dynamics for the fugacity $\lambda$, Hard-core model on the random graph $G(n, d/n)$. We show that for the typical instances of the random graph $G(n,d/n)$ and for fugacity $\lambda<\frac{d^d}{(d-1)^{d+1}}$, the mixing time of Glauber dynamics is $n^{1 + O(1/\log \log n)}$. Our result improves on the recent elegant algorithm in [Bezakova, Galanis, Goldberg Stefankovic; ICALP'22]. The algorithm there is a MCMC based sampling algorithm, but it is not the Glauber dynamics. Our algorithm here is simpler, as we use the classic Glauber dynamics. Furthermore, the bounds on mixing time we prove are smaller than those in Bezakova et al. paper, hence our algorithm is also faster. The main challenge in our proof is handling vertices with unbounded degrees. We provide stronger results with regard the spectral independence via branching values and show that the our Gibbs distributions satisfy the approximate tensorisation of the entropy. We conjecture that the bounds we have here are optimal for $G(n,d/n)$. As corollary of our analysis for the Hard-core model, we also get bounds on the mixing time of the Glauber dynamics for the Monomer-dimer model on $G(n,d/n)$. The bounds we get for this model are slightly better than those we have for the Hard-core model