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

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

1 ∑ ∑ [ ]
ρ f ρ (9)
( f, f) ⩽ t rel (P ℓ )·  
Var µ [ f] ⩽ t rel (P ℓ )·E P ℓ µ V\S (ρ)·Var µ S
n
  S ∈( ℓ )
V ρ∈Ω V\S
 
 
ℓ
 
ρ
ρ
ρ
,
其中, Ω V\S 表示边缘分布 µ V\S 的支撑集, f ρ : Ω → R 的定义为 f ρ (τ) ≜ f(ρ⊎τ) Ω 表示条件分布 µ 的支撑集. 对于
S S S
 
V
  ρ ρ
 
任何 S ∈   和 ρ ∈ Ω V\S , 令 P 表示条件分布 µ 上的 Glauber dynamics, 其中 Glauber dynamics 是定义 1 中的
ℓ S S
 
1-block dynamics. 根据命题 3, Glauber 动力学 P 是不可约的. 注意到 |S | = ℓ. 再次根据引理 1 和引理 2, 对于任何
ρ
S
ρ
f ρ : Ω → R, 有:

S
[ ] ( ρ ) ( ) ( ρ ) 1 ∑ ∑ ρ [ ]
ρ f ρ , f ρ ⩽ t rel P · µ ρ⊎σ f ρ⊎σ (10)
S S S \{v} (σ)·Var µ v
ℓ
Var µ S
ρ f ρ ⩽ t rel P ·E P S
v∈S σ∈Ω ρ
S \{v}
ρ
其中, µ ρ 是从 µ 投影到 S \{v} 上的边缘分布; Ω ρ ⊆ {0,1} S \{v} 是 µ ρ 的支撑集. 函数 ρ⊎σ → R 的定义为
S \{v} S S \{0} S \{v} f ρ⊎σ : Ω v
ρ⊎σ ρ⊎σ
,
f ρ⊎σ (c v ) = f ρ (σ⊎c v ), 其中 Ω v ⊆ {0,1} 是 µ v 的支撑集; σ⊎c v 表示 S 上的配置, 其中 v 的值为 c v ∈ {0,1} S \{v} 上
 
V
 
 
的配置为 σ. 对于任何 S ⊆  , 定义最大弛豫时间为:
 
ℓ
(
t max (S ) = max t rel P ρ ) (11)
S
rel
ρ∈Ω V\S
注意到, 方差是非负的. 结合公式 f : Ω → R, 有:
(9)–(11), 对于任意
1 ∑ ∑ 1 ∑ ∑ ρ [ ]
µ V\S (ρ)·t max (S )· µ
Var µ [ f] ⩽ t rel (P ℓ )·   rel S \{v} (σ)·Var µ v ρ⊎σ f ρ⊎σ
n ℓ ρ
  S ∈( ℓ ) v∈S σ∈Ω
 
V ρ∈Ω V\S
  S \{v}
ℓ
 
1 1 ∑ ∑ ∑ [ ]
rel
(∗) = t rel (P ℓ )· ( ) · t max (S ) µ V\{v} (ρ⊎σ)·Var µ v ρ⊎σ f ρ⊎σ
n ℓ ( V ) v∈S ρ∈Ω V\S
ℓ S ∈ ℓ σ∈Ω ρ S \{v}
1 1 ∑ ∑ ∑
∆ max [ ]
) · t (S ) µ V\{v} (τ)·Var µ τ f τ .
(令τ = ρ⊎σ) ⩽ t rel (P ℓ )· ( rel v
n ℓ ( V ) v∈V τ∈Ω V\{v}
ℓ S ∈ ℓ
注意, 在 (∗) 中, 我们列举了集合 S 中的所有顶点 v, 但在最后一行中, 我们列举了集合 V 中的所有顶点 v. 由
   
V V
   
    中均匀随机抽取的随机集合. 令 P 为
 
于 S ⊆ V 且所有变量都是非负的, 最后一个不等式成立. 设 S ∈   是从
   
ℓ ℓ
Glauber dynamics (1-block dynamics) 在 µ 上的转移矩阵, t rel (P) 表示其弛豫时间. 通过上述不等式, 对于任意函数
f : Ω → R, 有:

n [ ] 1 ∑ ∑ [ ]
max
Var µ [ f] ⩽ t rel (P ℓ )· ·E S t rel (S) · µ V\{v} (τ)·Var µ τ f τ
ℓ n v
v∈V τ∈Ω V\{v}

n [ ]
(根据引理2) = t rel (P ℓ )· ·E S t max (S) ·E P ( f, f).
rel
ℓ
其中, E P ( f, f) 是 Glauber dynamics P 的狄利克雷形. 通过公式 (5) 中 P 的 Poincaré不等式和公式 (1) 中弛豫时间的
定义, Glauber dynamics 的弛豫时间 t rel (P) 满足:

n [ ]
t rel (P) ⩽ t rel (P ℓ )· ·E S t max (S) .
rel
ℓ
为了证明引理 10, 只需证明:

[ ]
E S t max (S) ⩽ 3n (12)
rel
   
[ ] V V
 
 
 
 
为了给出 E S t max (S) 的上界, 我们将所有 S ∈   分类为好和坏情况. 固定一个 S ∈  , 让 G[S ] 表示 G 在 S
ℓ
rel    
ℓ
λ 为硬核模型实例的参数. 我们通过以下方式判断集合 S 是好还是坏.
上的导出子图. 令 ∆ G[S ] 表示 G[S ] 的最大度. 令
1
● 好集合: 如果 λ < ( ) , 则 S 是好的.
2 ∆ G[S ] +2