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

陈小羽 等: 吉布斯采样在临界点前的快速收敛 1619

定义 1. ℓ-block dynamics. 对于任意正整数 1 ⩽ ℓ ⩽ |V| µ 上的ℓ-block dynamics 是一个马尔可夫链 (X t ) t⩾0 , 定义
,
如下. 它从任意配置 X 0 ∈ Ω 开始, 在第 t 个转移步骤中, 执行如下操作.
 
V
 
 
● 均匀随机选择一个集合 S ∈  , 并使 X t (V\S ) = X t−1 (V\S ).
ℓ
 
● 从分布 µ X t (V\S ) 中采样 X t (S ) ∈ Ω X t (V\S ) .
S S
µ 上的 µ 上的 block dynamics, 其
σ
特别地, 1-block dynamics 其实就是 Glauber dynamics. 我们考虑在条件分布
Λ
σ
中 Λ ⊆ V 是一个子集, σ ∈ {0,1} V\Λ 是一个可行配置. 特别地, 如果 Λ = V, 则 µ = µ. 以下命题很容易验证.
Λ
σ
命题 3. 对于从硬核模型诱导出的任何条件分布 µ , 对于任何 1≤ℓ≤|Λ|, 在 µ 上的ℓ-block dynamics 是不可约
σ
Λ
Λ
σ
的、非周期的, 并且关于 µ 是时间可逆的.
Λ
2.4 分析工具
设 µ 是具有支撑集 Ω 的分布. 令 ⟨·,·⟩ µ 表示由 µ 加权的内积, 即, 对于任何两个函数 f,g : Ω → R,

∑
⟨ f,g⟩ µ ≜ µ(X) f(X)g(X).
X∈Ω
设 P 是一个不可约的马尔可夫链, 对于 µ 是时间可逆的. 我们通常将转移矩阵 P 视为一个马尔可夫算子, 将函
数映射到函数. 对于任何函数 f : Ω → R, P 作用在 f 上产生一个新的函数 Pf : Ω → R, 使得:

∑
(Pf)(X) ≜ P(X,Y) f(Y), ∀X ∈ Ω.
Y∈Ω
如果将 f 视为一个列向量, 那么 Pf 就是简单的矩阵乘法. 由于 P 是不可约且时间可逆的, P 有|Ω|个实特征值
1 = λ 1 > λ 2 ⩾ ... ⩾ λ |Ω| ⩾ −1 (因为 P 是不可约的, 所以 λ 2 < 1) [30] ; 每个 λ i 对应一个实特征函数 f i : Ω → R, 使得 Pf i =
Ω
λ i f i , 其中 f 1 = 1 为全 1 向量, 而 f 1 , f 2 ,..., f |Ω| 形成一个内积空间 ( R ,⟨·,·⟩ µ ) 的正交基. 假设 |Ω| ⩾ 2. P 的绝对谱隙定
义为 1−λ ⋆ ≜ 1−max{|λ i | | 2 ⩽ i ⩽ |Ω|} . P 的谱隙 (spectral gap) 定义为 1−λ 2 . P 的弛豫时间 (relaxation time) 定义为:

 1


 , if |Ω| ⩾ 2


1−λ ⋆ (1)
t rel (P) ≜ 



 0, if |Ω| = 1
在退化情况|Ω| = 1 t rel (P) = 0. 关于混合时间和弛豫时间之间的关系是众所周知的 [30] :
中, 我们简单假设
( )
1
T mix (ε) ⩽ t rel log , 其中µ min = min µ(X) (2)
εµ min X∈Ω
此外, 如果 P 是在 µ 上的一个不可约的 block dynamics (定义 1), 则 P 具有|Ω|个非负实特征值 1 = λ 1 > λ 2 ⩾ ... ⩾
[23,30,31]
λ |Ω| ⩾ 0 . 因此, 有以下关系成立:

1−λ ⋆ = 1−λ 2 .
在本文中, 我们将使用以下工具来分析谱隙.
2.4.1 Poincaré 不等式
对于任意 f : Ω → R, 关于 µ 的期望值被定义为:

∑
E µ [ f] ≜ µ(X) f(X).
X∈Ω
关于 µ 的方差被定义为:

[ ] ( ) 2 1 ∑
2
Var µ [ f] ≜ E µ f − E µ [ f] = µ(X)µ(Y)( f(X)− f(Y)) 2 (3)
2
X,Y∈Ω
2
2
其中, 2 f (x) = ( f(x)) . 设 P µ 时间可逆的马尔可夫链. 关于 P µ 的狄利克雷形定义为:
f 是一个函数, 使得 是关于 和
1 ∑
E P ( f, f) ≜ ⟨f,(I − P) f⟩ µ = µ(X)P(X,Y)(f(X)− f(Y)) 2 (4)
2
X,Y∈Ω
谱隙可以通过以下 Poincaré不等式来表征 [30] :