Page 177 - 《软件学报》2026年第4期

1618 软件学报 2026 年第 37 卷第 4 期

文的证明仅在这个新分布上考虑通过固定变量状态得到的一系列条件分布, 从而得到一个简单且初等的证明.

2 定义和背景知识

2.1 硬核模型和已知结果
V
设 I = (G = (V,E),λ) 是一个硬核模型, 其吉布斯分布为 µ = µ I . 在分析中, 我们经常把 µ 视为在 {0,1} 上的分
{ }
V
V Ω = Ω I = σ ∈ {0,1} | S σ 是一个独立集
布. 每个配置 σ ∈ {0,1} 代表一个唯一的子集 S σ ≜ {v ∈ V | σ v = 1}. 我们使用
,
|S σ |
来表示 µ 的支撑集. 对于每个 σ ∈ Ω µ(σ) ∝ λ .
对于硬核模型, Glauber dynamics 的谱隙和混合时间易于在 Dobrushin 条件下分析. 通过路径耦合 [26] 及其对谱
隙的推论 [27] , 我们得到以下结果. 类似的结果也在文献 [28] 中观察到.
命题 1 [26,27] . 设 0 < δ < 1 是一个常数. 设 I = (G,λ) 是具有最大度 ∆ ⩾ 1 的 n 顶点硬核模型. 如果 I 满足 Dobrushin
1−δ n n δ
λ ⩽ I 上的 log , 谱间隙至少为 .
条件 , 那么对于 Glauber dynamics, 其混合时间至多为
∆−1+δ δ ε n
基于局部到全局技术 [8,9,23] , 可以证明在唯一性区域中硬核模型有以下谱隙.
命题 2 . 令 δ ∈ (0,1) 为常数. 令 I = (G,λ) 为一个具有最大度数 ∆ ⩾ 3 的 n 顶点硬核模型. 如果 I 满足唯一性
[8]
条件 λ ⩽ (1−δ)λ c (∆), 那么 I 上 Glauber dynamics 的谱隙至少为 (5n) −66/δ .
注意到在文献 [8] 中的结果意味着 Glauber dynamics 有 n −1−32/δ −O( 1/δ 2 ) 的谱隙下界. 结合文献 [8] 和文献 [29]
e
的 Theorem 1.1 和 Theorem 3.1, 可以得到命题 2 中的结果.
2.2 马尔可夫链和混合时间
设 Ω 是 Ω 上的马尔可夫链, 其转移矩阵 P : R Ω×Ω . 当上下文清楚时,
(transition matrix) 为
为状态空间. 设
(X t ) t⩾0
⩾0
我们通常使用矩阵 P 来表示对应的马尔可夫链. 当对任意的 X,Y ∈ Ω, 存在整数 t 使得 P (X,Y) > 0 时, 马尔可夫链
t
是不可约 (irreducible) 的. 当对任意的 X ∈ Ω gcd{t | P (X,X) > 0} = 1 时, 马尔可夫链是非周期性 (aperiodic) 的. 如
,
t
果一个分布 µ 满足 µ = µP, 则称 µ 是 P 的一个稳态分布 (stationary distribution). 如果一个马尔可夫链既是不可约
µ, 马尔可夫链 P 满足下面的详细平衡方程
的又是非周期性的, 那么它有一个唯一的稳态分布. 如果对于分布
(detailed balance equation):

µ(X)P(X,Y) = µ(Y)P(Y,X), ∀X,Y ∈ Ω.
这意味着 µ 是 P 的一个稳态分布. 我们也说这个马尔可夫链是时间可逆的 (time reversible). 在本文中, 我们考
虑的所有马尔可夫链都是可逆的.
令 µ 是集合 Ω 上的分布. 令 P 是一个关于 Ω 的不可约、非周期、时间可逆的马尔可夫链, 具有唯一的稳态分
布 µ. P 的混合时间的定义为:

{ ( t ) }
T mix (ε) ≜ maxmin t | d TV P (X,·),µ ⩽ ε , ∀0 < ε < 1,
X∈Ω
t
t
t
其中, P (X,·) 是从 X 开始经过 t 个转移步骤后生成的分布的马尔可夫链, d TV (P (X,·),µ) 表示 P (X,·) 和 µ 之间的全
变差距离 (total variation distance), 形式上为:

1 ∑
)
(
d TV P (X,·),µ ≜ P (X,Y)−µ(Y).
t
t

2
Y∈Ω
2.3 Block dynamics
在本文中, 我们研究布尔随机变量上的 block dynamics. 设 V 是一个基底集合. 设 µ 是定义在 {0,1} 上的分布,
V
支撑集为 Ω. 对于任意 Λ ⊆ V , 我们用 µ Λ 表示从 投影到 Λ 上的边缘分布. 对于某些集合 Λ ⊆ V 上的配置
µ
τ
Λ V\Λ µ 表示在给定 条件下 上的
σ ∈ {0,1} , 如果 µ Λ (σ) > 0, 则我们称 σ 是可行的. 对于任意可行的 τ ∈ {0,1} , 令 τ Λ
Λ
 
V
τ Λ τ  
 
边缘分布. 我们用 Ω ⊆ {0,1} 来表示 µ 的支撑集. 对于任意整数 1 ⩽ ℓ ⩽ |V|, 令   ≜ {S ⊆ V||S |= ℓ} 表示所有大小
ℓ
Λ Λ  
为ℓ的子集的集族. µ 上的 block dynamics 定义如下.