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

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

{ }

E P ( f, f)
1−λ 2 = inf f : Ω → R,Var µ [ f] , 0 (5)

Var µ [ f]
此外, 如果 P 是 µ 上的 block dynamics (定义 1), 我们有以下性质.
引理 1. 设 V 是一个基底集合. 设 µ 是在 {0,1} 上的支撑集为 Ω 的分布. 令 1 ⩽ ℓ ⩽ |V| 是一个整数. 令 P 是 µ 上
V
的ℓ-block dynamics. 如果 P 是不可约的, 那么:

Var µ [ f] ⩽ t rel (P)E P ( f, f), ∀ f : Ω → R.
证明: 如果|Ω| ≥ 2, 由于 P 是不可约的, λ 2 < 1, 因此根据公式 (5), 命题成立. 如果|Ω| = 1, 那么根据公式 (3) 和
公式 (4) 中的定义, 我们有 Var µ [ f] = E P ( f, f) = 0, 因此命题显然成立.
此外, 块动态的狄利克雷形可以用引理 2 [32,33] 来重新表述. 对于任意不相交集合 A,B ⊆ V , 任意 σ A ∈ {0,1} ,
A
B A∪ B 上的配置, 该配置在 σ A 一致, 在
σ B ∈ {0,1} , 我们用 σ A ⊎σ B 表示一个在 A 中与 B 中与 σ B 一致.
引理 2. 设 V 是一个基底集合. 设 µ 是一个在 {0,1} 上支撑集为 Ω 的分布. 设 1 ⩽ ℓ ⩽ |V| 为一个整数. 设 P 是 µ
V
上的ℓ-block dynamics. 对于任意 f : Ω → R, 有:

1 ∑ ∑ [ ]
ρ f ρ ,
E P ( f, f) =   µ V\S (ρ)·Var µ S
  S ∈( ℓ)
n
 
v ρ∈Ω V\S
 
 
ℓ
ρ
ρ
ρ
其中, Ω V\S 表示边缘分布 µ V\S 的支撑集, f ρ : Ω → R 定义为 f ρ (τ) ≜ f(ρ⊎τ), 而 Ω 表示条件分布 µ 的支撑集.
S
S
S
证明: 通过ℓ-block dynamics 的定义, 我们知道对于所有的 σ,τ ∈ Ω, 转移概率可以写成:

1 ∑ σ V\S [ ]
µ (τ S )·1 σ V\S = τ V\S .
P(σ,τ) =   S
n
V
  S ∈( ℓ )
 
 
 
ℓ
于是, 根据公式 (4) 中狄利克雷形的定义, 我们有:

1 ∑ 1 ∑ [ ]
E P ( f, f) = µ(σ)  µ σ V\S (τ S )·1 σ V\S = τ V\S ·( f(σ)− f(τ)) 2
2 S
σ,τ∈Ω n V
  S ∈( ℓ )
 
 
ℓ
 
1 ∑ ∑ 1 ∑ ρ ρ ( ) 2
µ V\S (ρ)· µ (α)µ (β) f ρ (α)− f ρ (α)
=   S S
2
n ρ
  S ∈( ℓ ) α,β∈Ω S
 
V ρ∈Ω V\S
 
 
ℓ
1 ∑ ∑ [ ]
ρ f ρ .
=   µ V\S (ρ)·Var µ S
n
  S ∈( ℓ )
 
V ρ∈Ω V\S
 
ℓ
 
2.4.2 Cheeger 不等式
∑
设 P 是相对于 µ 可逆的马尔可夫链. 对于状态空间的任意子集 S ⊆ Ω, 我们使用 µ(S ) 表示 µ(X). 马尔可
X∈S
夫链 P 的导通率 (conductance) 定义为:

∑
µ(X)P(X,Y)
Φ ≜ min X∈S,Y∈Ω\S .
S ⊆Ω:µ(S )⩽1/2 µ(S )
命题 4. Cheeger 不等式 [34,35] . 导通率和谱隙满足如下关系:

Φ 2
⩽ 1−λ 2 ⩽ 2Φ.
2
2.5 集中度
我们将使用以下超几何分布的概率集中不等式.
   
V
引理 3 [36] . 设 V 为大小为 n 的基底集合. 设 Λ ⊆ V 为一个子集. 给定一个整数 1 ⩽ ℓ ⩽ n, 令 S ∈   为从 V
  中
 
 
 
 
ℓ
 
ℓ  