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

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

|S | ℓ
( σ ) ( σ⊎τ ) ( σ⊎τ )
t rel P S = ·t rel P A = ·t rel P A (15)
|A| |A|
( σ⊎τ ) σ⊎τ
我们现在要界定 t rel P . 注意到 P 恰好是硬核模型实例 I = (G[A],λ) 上的 Glauber dynamics, 其中 G[A]
A A
是 G 在 A 上的导出子图. 注意到 ∆ G[A] ⩽ ∆ G[S ] ⩽ ∆ G .
1 1
如果 S ∈ G. 则有 λ ⩽ ( ) , 这意味着 λ ⩽ ( ) . 在这种情况下, 我们要证明:
2 ∆ G[S ] +1 2 ∆ G[A] +1

( σ⊎τ )
t rel P A ⩽ 2|A| (16)
然后, 结合公式 (15) 和公式 (16) 证明引理. 如果 ∆ G[A] = 0, 那么 A 中的所有变量是独立的, 公式 (16) 显而易见.
∆ G[A] ⩾ 1, 那么根据命题 I 满足 Dobrushin 条件, ( σ⊎τ )
如果 1, 实例 δ = 1/2. 因此, 依然有弛豫时间 t rel P A ⩽ 2|A|.
( )
假设 S ∈ B. 由于 I 在唯一性区域内, 我们有 λ ⩽ (1−δ)λ c (∆ G ) ⩽ (1−δ)λ c ∆ G[A] . 因此, 实例 J ∈ F(δ) 也处于唯
一性区域内. 我们考虑以下两种情况.
● 情况 1: ∆ G[A] ⩾ 3. 根据命题 2, 有 t rel P σ⊎τ ) ⩽ (5|A|) 66/δ .
(
A
1 1 1
● 情况 2: ∆ G[A] ⩽ 2. 注意到 λ < λ c (∆ G ). 由于 ∆ G ⩾ 20, 有 λ ⩽ λ c (20) ⩽ . 由于 ∆ G[A] ⩽ 2, 有 λ ⩽ ⩽ ( ) .
6 6 2 ∆ G[A] +1
( σ⊎τ ) 66/δ
根据该情况的证明, 我们有 t rel P ⩽ 2|A| ⩽ (5|A|) .
A
根据公式 |A| ⩽ ℓ, 我们有:
(15) 和
ℓ
( σ ) 66/δ 70/δ
t rel P S ⩽ ·(5|A|) ⩽ (5ℓ) .
|A|
⌊ ⌋
n ( )
因为 ℓ = 和 n≥12000, 这意味着ℓ≥100. 所以我们有 t rel P µ σ ⩽ ℓ 140/δ .
32e S
5 Glauber dynamics 之间的比较
在本节中, 我们证明引理 7. 设 I = (G = (V,E),λ) 是图 G 上的硬核模型实例. 令 k ∈ N 是一个正整数. 在实例 I
+
上使用 k-变换 (定义 3), 我们定义以下转换后的实例:

λ
′
I = (G ,λ ) ≜ Trans(I,k), G = (V ,E ), λ = .
′
′
′
′
′
′
k
′ ′ µ 的支撑集是 µ 的支撑集是 Ω′. 令 P 分别表示
′
′
令 µ 和 µ 分别表示由 I 和 I 诱导的吉布斯分布, 其中 Ω, P 和
′
在 I 和 I 上的 Glauber dynamics 的转移矩阵. 我们证明以下一般情形下的比较引理.
引理 12. 比较引理. 对于任何 k ∈ N , 任何硬核模型实例 I = (G,λ), 让 I = Trans(I,k) 表示变换后的实例, P 和
+
′
P 的谱隙满足:
′

k +λ
1−λ 2 (P) ⩾ (1−λ 2 (P )).
′
1+λ
+ I 超出了唯一性阈值. 很容易验证引理 7
注意, 上述引理对于任何 k ∈ N 和任何硬核模型实例 I 都成立, 即使
是引理 12 的推论. 让 Δ 表示 G 的最大度数. 在引理 7 中, 对于 Δ≥3, 有 λ < λ c (∆ G ) ⩽ 4. 根据公式 (6), 我们有 κ(I) = k ⩾ 5,
k +λ k
因此 ⩾ . 本节的其余部分将专注于证明引理 12. 为了证明引理 12, 引入一个新的链 P lazy , 该链位于状态空
1+λ 5
1+λ
间 Ω 上, 是 Glauber dynamics P 的一个懒化版本. 定义 r ≜ 1− , 可以很容易验证 0 ⩽ r < 1 P lazy 的转移规则定
.
k +λ
义如公式 (17). 在每个转移步骤中, 以概率 r, 链 P lazy 停留在当前状态; 否则, 它将执行与链 P 相同的更新. 转移矩
P lazy 和 P 有以下关系:
阵

P lazy = rI +(1−r)P (17)
其中, I ∈ R Ω×Ω 为单位矩阵. 很容易验证 P ne 是不可约的、非周期性的, 并且关于 µ 是时间可逆的. 我们首先比较
w
y
P 和 P lazy , 然后比较 P laz 和 y P'. 根据公式 (17) 中 P laz 的定义, 容易验证引理 13.
(
(
引理 13. 1−λ 2 (P) = 1 ( 1−λ 2 P lazy )) = k +λ ( 1−λ 2 P lazy )) .
1−r 1+λ
然后, 我们有引理 14.