吉布斯采样在临界点前的快速收敛
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP301

基金项目:


Rapid Convergence of Gibbs Sampling Before the Critical Point
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    吉布斯采样的临界行为是计算相变理论所关注的核心问题. 以硬核模型这一经典模型为例, 研究了吉布斯采样在临界点前的快速收敛. 在该模型中, 给定一个最大度为Δ≥3的n顶点图G以及参数λ≥0, 则图G中的每个独立集S以正比于λ|S|的概率被采样. 研究了实现这一采样的经典吉布斯采样算法——Glauber dynamics, 在临界条件λ<(Δ–1)Δ–1/(Δ–2)Δ下, 证明了该采样过程的马尔可夫链具有渐进最优的谱隙为Ω(1/n), 因此这一经典采样算法在该临界点前始终快速收敛.吉布斯采样过程在临界点前的快速收敛是马尔可夫链蒙特卡洛(MCMC) 理论中的一类重要问题. 针对硬核模型上的这一问题, 此前已有若干依赖高等数学工具的证明. 为这个重要问题提供了一个简化的组合证明, 引入计算复杂性归约的思想来分析采样过程的收敛速率.

    Abstract:

    The critical behavior of Gibbs sampling is a central issue in the theory of computational phase transitions. This study takes the hard-core model, a classical model, as an example to study the rapid convergence of Gibbs sampling before the critical point. In this model, given an n-vertex graph G with a maximum degree of Δ≥3 and a parameter λ≥0, each independent set S in graph G is sampled with a probability proportional to λ|S|. This study investigates the canonical Gibbs sampling algorithm, Glauber dynamics, which implements this sampling. Under the critical condition λ<(Δ–1)Δ–1/(Δ–2)Δ, it is proven that the Glauber dynamics has an asymptotically optimal spectral gap of Ω(1/n), thus establishing that this classical sampling algorithm mixes rapidly up to the critical point. The rapid convergence of the Gibbs sampling process before the critical point is an important issue in Markov chain Monte Carlo (MCMC) theory. For this problem on the hard-core model, several proofs relying on advanced mathematical tools have been previously provided. This study offers a simplified combinatorial proof for this significant problem, introducing the idea of reductions from computational complexity to analyze the convergence rate of the sampling process.

    参考文献
    相似文献
    引证文献
引用本文

陈小羽,凤维明,尹一通,张昕渊.吉布斯采样在临界点前的快速收敛.软件学报,2026,37(4):1615-1633

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2025-03-01
  • 最后修改日期:2025-08-23
  • 录用日期:
  • 在线发布日期: 2025-12-10
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号