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

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


−1
 g (σ) = k |σ|




( )|σ| .

 λ
 −1
 ′ ′ ′
∀σ ∈ g (σ),w (σ ) =

k
对于任意 σ ∈ Ω, 有:

λ ∑
( )|σ|
|σ| |σ| ′ ′
w(σ) = λ = k · = w (σ ).
k
σ ′ ∈g −1 (σ)
由于 g 是从 Ω′到 Ω 的映射, 我们有:

∑ ∑ ∑ ∑
′
′
′
′
′
Z = w (σ ) = w (σ ) = w(σ) = Z.
σ ′ ∈Ω ′ σ∈Ω σ ′ ∈g −1 (σ) σ∈Ω
这意味着, 对于任何 σ ∈ Ω, 有:

∑
′
′
w (σ )
w(σ) σ ′ ∈g −1 (σ) ∑
′
µ(σ) = = = µ (σ ).
′
Z Z ′
σ ′ ∈g −1 (σ)
然后, 证明公式 (19). 固定两个配置 σ,τ ∈ Ω. 令 σ⊕τ ≜ {v ∈ V | σ v , τ v } 表示 σ 和 τ 之间的不一致顶点集. 固定
σ ∈ g (σ). 我们考虑以下 3 种情况 |σ⊕τ| 分类).
−1
′
一个配置 (以
−1
′
● 假设 |σ⊕τ| > 1. 在这种情况下, P lazy (σ,τ) = 0, 因为 P lazy 每一步只更新一个顶点. 固定一个配置 τ ∈ g (τ). 很
′ ′ ′ ′ ′
容易验证 |σ ⊕τ | ⩾ |σ⊕τ| > 1. 因此 P (σ ,τ ) = 0, 最后一个性质成立.
,
● 假设 |σ⊕τ| = 1. 这里有两种情况. 首先假设存在一个顶点 v ∈ V , 使得 σ v = 1 τ v = 0, 且对所有 u ∈ V\{v},
(1−r)
σ u = τ u . 在这种情况下, 根据公式 (17), 有 P lazy (σ,τ) = , 其中 n = |V|. 考虑链 , 回顾此前, 我们有 σ ∈ g (σ).
−1
P
′
′
n(1+λ)
−1
′
′
′
′
′
在团 C v 中恰有一个顶点 , 使得 σ = 1. 在链 P 中, 从 σ 移动到 τ ∈ g (τ) 的唯一可能性是 P 选择顶点 v i 并将 v i
v i
v i
1+λ
的值更新为 0. 记为 r ≜ 1− , |V | = kn. 因此, 我们有:
′
k +λ
∑ 1 1 1−r
′
′
P (σ ,τ ) = = = = P lazy (σ,τ).
′
kn(1+λ ) n(k +λ) n(1+λ)
′
τ ′ ∈g −1 (τ)
,
,
现在假设存在一个顶点 v ∈ V, 使得 σ v = 0 τ v = 1, 且对所有 u ∈ V\{v} σ u = τ u . 在这种情况下, 根据公式 (17),
(1−r)λ
−1
′
′
′
′
有 P lazy (σ,τ) = . 考虑链 P . 回顾此前, 我们有 σ ∈ g (σ). 所有团 C v 中的顶点 v i 都满足 σ = 0. 在链 P 中,
n(1+λ) v i
′ ′ −1 ′ v i 的值更新为 1. 因此, 我们有:
从 σ 移动到 τ ∈ g (τ) 的唯一可能性是 P 选择团 C v 中的一个顶点 v i 并将

kλ λ (1−r)λ
∑ ′
P (σ ,τ ) = = = = P lazy (σ,τ).
′
′
′
kn(1+λ ) n(k +λ) n(1+λ)
′
τ ′ ∈g −1 (τ)
′
′
′
′
● 假设 |σ⊕τ| = 0, 这意味着 σ = τ. 注意马尔可夫链 P 每一步只更新一个顶点. 因此, P (σ ,τ ) > 0 当且仅当
′ ′ ′ ′ ′ ′ ′ ′ ′
|σ ⊕τ | ⩽ 1. 这意味着 P (σ ,τ ) > 0, 当且仅当 |g(σ )⊕g(τ )| = |σ⊕g(τ )| ⩽ 1. 由于 P 是随机矩阵, 所以:

∑ ∑ ∑ ∑ ∑
′
′
′
′
′
′
′
′
P (σ ,τ ) = P (σ ,τ ) = P (σ ,τ )+ P (σ ,τ ) = 1.
′
′
′
′
τ ′ ∈Ω ′ τ ′ ∈Ω ′ τ ′ ∈g −1 (σ) τ∈Ω τ ′ ∈g −1 (τ)
|σ⊕g(τ ′ )|⩽1 |σ⊕τ|=1
同样, P laz 也每一步只更新一个顶点, 我们有:
y

∑ ∑
P lazy (σ,τ) = P lazy (σ,σ)+ P lazy (σ,τ) = 1.
τ∈Ω τ∈Ω
|σ⊕τ|=1
因此, 可以证明:

∑
′
′
P (σ ,τ ) = P lazy (σ,τ), ∀τ ∈ Ω with |σ⊕τ| = 1.
′
τ ′ ∈g −1 (τ)
∑
′
′
′
通过对比, 我们得出 P (σ ,τ ) = P lazy (σ,σ).
τ ′ ∈g −1 (σ)
现在证明引理 f : Ω → R 为:
′
′
15. 给定一个满足 Var µ [ f] , 0 的函数 f : Ω → R, 定义