软件学报

作者：陈小羽，凤维明，尹一通，张昕渊

单位：陈小羽，计算机软件新技术全国重点实验室(南京大学), 新基石科学实验室, 江苏 南京 21002311,凤维明，香港大学 计算与数据科学学院, 香港 99907702,尹一通，计算机软件新技术全国重点实验室(南京大学), 新基石科学实验室, 江苏 南京 21002303,张昕渊，计算机软件新技术全国重点实验室(南京大学), 新基石科学实验室, 江苏 南京 21002304

关键词：计算相变;马尔可夫链蒙特卡洛方法;硬核模型

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

来源：2026年第4期

《软件学报》期刊编辑部

查看软件学报杂志2026年第4期