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

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

我们使用以下特定的变换来证明引理 I = (G,λ) ∈ F(δ), 定义参数:
4. 设 0 < δ < 1 为常数. 对于任意
⌈ 6 ⌉
10
κ(I) ≜ logn (6)
δ 2
其中, n 为 G 中的顶点数. 定义转换后的实例:

′
′
′
′
I = (G = (V ,E ),λ ) ≜ Trans(I,κ(I)) (7)
′
我们有以下两个引理.
引理 6. Glauber dynamics 在 I 上的谱隙. 设 0 < δ < 1 为一个常数. 存在一个常数 C 1 (δ) = exp(O(1/δ)) 使得对于
′
I = (G ,λ ) 上 Glauber dynamics 的谱隙 (参照公式 (7) 中
′
′
′
任意 I = (G,λ) ∈ F(δ), 如果 ∆ ⩾ 8/δ, 那么对于转换后实例
的定义) 满足:

1
γ I ′ ⩾ ,
C 1 (δ)n ′
′
其中, Δ 是图 G 的最大度数, n 是图 G 的顶点数.
′
引理 I 上 ′ I = (G,λ) ∈ F(δ), 有:
7. 在 I 和 Glauber dynamics 的比较. 设 0 < δ < 1 为常数. 对于任意
κ(I)
γ I ⩾ γ I ′,
5
其中, γ I 是 I 上 Glauber dynamics 的谱隙, γ I ′ 是变换后实例 I 上 ′ Glauber dynamics 的谱隙 (见公式 (7) 中定义),
κ(I) 是在公式 (6) 中定义的参数.
引理 6 的证明在第 4 节给出. 变换后, 新的实例 I 仍然处于唯一性区域, 其最大度数足够大. 最大度数的下界
′
保证了某种概率集中性质, 对我们的证明起着重要作用. 引理 7 的证明在第 5 节中给出. k-变换保证了存在一个函
X ∈ Ω I ′ 服从 Y = g(X) 服从 µ I . 使用此函数, 我们将两个马尔
数 g : Ω I ′ → Ω I , 如果 Gibbs 分布 µ I ′ , 那么 Gibbs 分布
可夫链联系起来, 以证明引理 7 中的关系. 有了引理 6 和引理 7, 我们现在来证明引理 4.
I = (G = (V,E),λ) ∈ F(δ). 如果 G 的最大度数 Δ< δ/8, 那么根据引理 5,
证明: 令 0 < δ < 1 为常数. 考虑一个实例
( ) O(1/δ)
1 1
′
谱隙至少为 , 其中 C 0 (δ) = 是引理 5 中的常数. 假设 ∆ ⩾ δ/8. 设 I 表示公式 (7) 中的变换实例. 结合
C 0 (δ)n δ
引理 6 和引理 7, 谱隙满足:

κ(I) κ(I) 1 1
γ I ⩾ γ I ′ ⩾ · = ,
5 5 C 1 (δ)n ′ 5C 1 (δ)n
其中, C 1 (δ) = exp(O(1/δ)) 是引理 6 中的常数, n 是 I 中顶点的数量, 最后一个等式成立是因为 n = κ(I)n. 将两种
′
′
′
1
情况结合起来, 谱隙 γ I 至少为 , 其中:
C(δ)n
( ) O(1/δ)
1
C(δ) = max{C 0 (δ),C 1 (δ)} = . □
δ
3.2 定理 1 的证明
0 < δ < 1. 固定一个具有 |V| = n. 设 Ω
固定一个常数 Gibbs 分布 µ 的实例 I = (G = (V,E),λ) ∈ F(δ), 其中 表示 µ
1
λ ⩾ . 否则, 由于 Dobrushin 条件成立, 根据命题 1, 主要结果成立. 令 P I 上的
的支撑集. 我们可以假设 表示
2∆
1
Glauber dynamics. 根据引理 4, P 的谱隙至少为 , 其中 C(δ) = (1/δ) O(1/δ) 是引理 4 中的常数. 注意, Glauber
C(δ)n
dynamics 是定义 1 中 block dynamics 的特例. 结合引理 4、公式 (1) 和公式 (2), 混合时间满足:

( )
1
T mix (ε) ⩽ C(δ)nlog , µ min = min µ(X).
X∈Ω
εµ min
∑ w(σ)
∑
V µ(σ) =
给出配置 σ ∈ {0,1} , 它的权重定义为 w(σ) = λ v∈V σ D . 设 Z = w(σ) 表示配分函数. 吉布斯分布由
σ∈Ω Z
定义.
∑
∑
Z ⩽ λ σ∈V σ v n w(σ) ⩾ min{1,λ }. 这意味着:
n
注意到 = (1+λ) , 而

σ∈{0,1}v