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

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

(
引理 14. 1−λ 2 P lazy ⩾ 1−λ 2 (P ).
)
′
引理 12 是通过结合引理 13 和引理 14 来证明的. 第 5.1 节专门用来证明引理 14.
5.1 引理 14 的证明
我们使用引理 15 来证明引理 14. 回想一下, P laz 的状态空间是 Ω, P laz 的稳态分布是 µ; P 的状态空间是 Ω′,
y
y
′
P 的稳态分布是 ; 狄利克雷形 .(·, ·) 和方差 Var.[·] 在公式 (4) 和公式 (3) 中定义.
µ
′
′
E
引理 ′ ′ Var µ ′ f , 0, 并且:
[ ]
′
15. 对于任何满足 Var µ [ f] , 0 的函数 f : Ω → R, 存在一个函数 f : Ω → R, 使得
( f, f) E P ′ ( f , f )
′
′
E P lazy
= .
Var µ ( f) Var µ ′ ( f )
′
引理 15 的证明见第 5.2 节. 现在我们来证明引理 14.
{ } { }
′
证明: 定义 W Ω = f : Ω → R | Var µ [ f] , 0 以及 W Ω ′ = f : Ω → R | Var µ ′[ f] , 0 . 根据引理 15, 存在一个从 W Ω 到
W Ω ′ 的映射 h, 对于任何 f ∈ W Ω , 我们有:

( f, f)
E P lazy E P ′(h( f),h( f))
= ,
Var µ ( f) Var µ ′(h( f))
其中, h( f) = f , f 是引理 15 h(W Ω ) 来表示 h h(W Ω ) ⊆ W Ω ′, 有以下关系:
′
′
中的函数. 我们使用 的像空间. 由于
( f, f) E P ′ ( f , f ) E P ′ ( f , f )
′
′
′
′
( ) E P lazy
1−λ 2 P lazy = inf = inf ⩾ inf = 1−λ 2 (P ). □
′
f∈W Ω Var µ [ f] f ′ ∈h(W Ω ) Var µ ′ ( f ) f ′ ∈W Ω ′ Var µ ′ ( f )
′
′
5.2 证明引理 15
为了证明引理 15, 我们定义函数 g. 回想一下 I = (G = (V,E),λ) 是原始的硬核模型实例, I = (G = (V ,E ),λ ) =
′
′
′
′
′
′
Trans(I,k) 是转化后的实例. 对于任意顶点 v ∈ V, 图 G 中有一个包含顶点 v 1 ,v 2 ,...,v k 的团.
定义 ′ σ ∈ Ω σ = g(σ ) 构造如下:
′
′
′
,
4. 设 g : Ω → Ω 是一个函数, 使得对于任何

 1, 如果存在1 ⩽ i ⩽ k使得σ (v i ) = 1
′


∀v ∈ V, σ v ≜  .

 0, 否则
−1 ′ τ 的原像, 则以下性质成立.
对于任意 τ ∈ Ω, 我们使用 g (τ) ⊆ Ω 来表示
引理 16. 函数 g 是一个从 Ω'到 Ω 的映射, 并且满足如下条件.
● 对于任意 σ ∈ Ω, 都有:

∑
µ (σ) = µ(σ) (18)
′
σ ′ ∈g −1 (σ)
′
′ ′ g(X ) ∼ µ.
这意味着如果 X ∼ µ , 那么
−1
′
● 对于任意 σ,τ ∈ Ω, 任意 σ ∈ g (σ), 都有:

∑
′
′
′
P (σ ,τ ) = P laxy (σ,τ) (19)
τ ′ ∈g −1 (τ)
( ) ( ( ))
′
′
这意味着如果 X 是马尔可夫链 P', 那么 g X 是马尔可夫链 P lazy .
t t⩾0 t t⩾0
证明: 根据定义 3, 对于图 G = (V,E) 中的任意顶点 v, G = (V ,E ) 中都存在一个包含顶点 v 1 ,v 2 ,...,v k 的 k-团
′
′
′
C v . 对于图 G 中的任意边 {u,v}, 在 G 中, C u 和 C v 中的所有顶点对都是相邻的. 对于任意配置 σ ∈ Ω ⊆ {0,1} , 集
V
′
′
′
′ ′ ′ ′ ′ S (σ ) 中, 那么对于 G 中的所
′
′
合 S (σ ) ≜ {v ∈ V | σ v = 1} 是 G 中的一个独立集, 这意味着如果 C v 中的某个顶点在
,
′
′
′
有边 {u,v} C u 中的任意顶点都不在 S (σ ) 中. 根据 g 的定义, 很容易看出 g(σ ) 表示 G 中的一个独立集. 这意味着
∑
g 是一个从 Ω′到 Ω 的映射. 对于任意配置 σ ∈ Ω, 我们用 |σ| 表示 σ v , 它的权重定义为 w(σ) ≜ λ . 让 Z ≜
|σ|
v∈V
∑ ∑
′ ′ ′ σ , 它
′
w(σ) 表示硬核模型实例 I = (G = (V,E),λ) 的配分函数. 对于任意配置 σ ∈ Ω , 我们用 |σ | 表示
σ∈Ω v∈V ′ v
∑
|σ ′ |
′ |σ ′ |
′
′
′
′
′
′
′
′
′
′
的权重定义为 w (σ ) ≜ (λ ) = (λ/k) . 让 Z ≜ w (σ ) 表示硬核模型实例 I = (G = (V ,E ),λ = λ/k) 的配分
σ ′ ∈Ω ′
−1 ′ ′ −1 v i 满足
函数. 固定配置 σ ∈ Ω. 考虑集合 g (σ) ⊆ Ω . 假设 σ ∈ g (σ). 如果 σ v = 1, 那么团 C v 中有且只有一个顶点
′ ′
σ = 1; 如果 σ v = 0, 那么对于 C v 中的所有顶点 , 都有 σ = 0. 因此, 我们有:
v i

v i v i