1 Markov 链
Markov 过程是指下一时刻的状态只与当前时刻的状态有关, 而与之前的状态无关, 用概率描述就是
𝑝(𝑥
𝑛
|𝑥
𝑛−1
, 𝑥
𝑛−2
, · · · , 𝑥
1
) = 𝑝(𝑥
𝑛
|𝑥
𝑛−1
)
其对应的态序列称为 Markov 链
(𝑥
1
, 𝑥
2
, · · · , 𝑥
𝑛
)
状态 𝑥 具有多种可能的取值, 不妨记为
𝑥 = {𝑥
(1)
, 𝑥
(2)
, · · · , 𝑥
( 𝑁 )
}
记 𝑊
𝑖 𝑗
为从状态 𝑥
(𝑖)
转移到状态 𝑥
( 𝑗 )
的概率, 即
𝑊
𝑖 𝑗
= 𝑝(𝑥
( 𝑗 )
|𝑥
(𝑖)
)
假定系统在 𝑡 时刻处于各状态的概率为
𝑝
𝑡
(𝑥
(𝑖)
) = 𝑝
𝑖
则在 𝑡 + 1 时刻处于各状态的概率为
𝑝
𝑡+1
(𝑥
( 𝑗 )
) =
𝑁
Õ
𝑖=1
𝑝
𝑖
𝑊
𝑖 𝑗
这可以写为矩阵
©
«
𝑝
1
𝑝
2
.
.
.
𝑝
𝑁
ª
®
®
®
®
®
®
¬
→
©
«
𝑊
11
𝑊
12
· · · 𝑊
1𝑁
𝑊
21
𝑊
22
· · · 𝑊
2𝑁
.
.
.
.
.
.
.
.
.
.
.
.
𝑊
𝑁 1
𝑊
𝑁 2
· · · 𝑊
𝑁 𝑁
ª
®
®
®
®
®
®
¬
©
«
𝑝
1
𝑝
2
.
.
.
𝑝
𝑁
ª
®
®
®
®
®
®
¬
这样进行多次后, 会存在一个极限分布, 即
lim
𝑛→∞
𝑊
𝑛
p = π
这个极限分布 π 称为平稳分布, 满足
π = 𝑊 π
这意味着平衡后状态的分布不会改变. 为了得到平稳分布存在的条件, 考察一个状态 𝑥
(𝑖)
, 它的布居有一
定概率转移到别的状态
Δ𝑝
−
=
Õ
𝑗
𝑝(𝑥
(𝑖)
) 𝑊
𝑖 𝑗
而别的状态的布居也有一定概率转移到 𝑥
(𝑖)
Δ𝑝
+
=
Õ
𝑗
𝑝(𝑥
( 𝑗 )
) 𝑊
𝑗𝑖
若达到平衡, 则系统在各状态的布居不再改变, 即转移走的布居等于转移来的布居
Õ
𝑗
𝜋(𝑥
(𝑖)
) 𝑊
𝑖 𝑗
=
Õ
𝑗
𝜋(𝑥
( 𝑗 )
) 𝑊
𝑗𝑖
也就得到了细致平衡条件
𝜋(𝑥
(𝑖)
) 𝑊
𝑖 𝑗
= 𝜋(𝑥
( 𝑗 )
) 𝑊
𝑗𝑖
可以进一步推广到连续的情形, 设状态 𝑥 的概率密度为 𝑝(𝑥), 则细致平衡条件为
𝑝(𝑥)𝑊 ( 𝑥 → 𝑥
′
) = 𝑝(𝑥
′
) 𝑊 (𝑥
′
→ 𝑥)
2 Metropolis 抽样
Metropolis 将概率矩阵 𝑊 分解为两部分
𝑊 (𝑥 → 𝑥
′
) = 𝑇 (𝑥 → 𝑥
′
) 𝐴(𝑥 → 𝑥
′
)
即从状态 𝑥 转移到 𝑥
′
的概率分为两步, 先由系统选择一个候选状态 𝑥
′
, 然后由环境决定是否接受 𝑥
′
. 系
统选择候选状态的概率为 𝑇 (𝑥 → 𝑥
′
), 接受的概率为 𝐴(𝑥 → 𝑥
′
)
Metropolis 取转移概率是对称的, 即
𝑇 (𝑥 → 𝑥
′
) = 𝑇 (𝑥
′
→ 𝑥)
然而接受概率不对称, 它是由目标分布 𝑝(𝑥) 决定的
𝐴(𝑥 → 𝑥
′
) =
1 𝑝(𝑥
′
) ≥ 𝑝(𝑥)
𝑝(𝑥
′
)
𝑝(𝑥)
𝑝(𝑥
′
) < 𝑝(𝑥)
那么概率矩阵 𝑊 就可以写为
𝑊 (𝑥 → 𝑥
′
) =
𝑇 (𝑥 → 𝑥
′
) 𝑝(𝑥
′
) ≥ 𝑝(𝑥)
𝑇 (𝑥 → 𝑥
′
)
𝑝(𝑥
′
)
𝑝(𝑥)
𝑝(𝑥
′
) < 𝑝(𝑥)
验证它满足细致平衡条件是简单的, 若 𝑝(𝑥
′
) ≥ 𝑝(𝑥), 则
𝑝(𝑥)𝑊 ( 𝑥 → 𝑥
′
) = 𝑝(𝑥)𝑇 (𝑥 → 𝑥
′
) = 𝑝(𝑥
′
)𝑇 ( 𝑥
′
→ 𝑥) = 𝑝(𝑥
′
) 𝑊 (𝑥
′
→ 𝑥)
若 𝑝(𝑥
′
) < 𝑝(𝑥), 则
𝑝(𝑥)𝑊 ( 𝑥 → 𝑥
′
) = 𝑝(𝑥)𝑇 (𝑥 → 𝑥
′
)
𝑝(𝑥
′
)
𝑝(𝑥)
= 𝑝(𝑥
′
)𝑇 ( 𝑥
′
→ 𝑥) = 𝑝(𝑥
′
) 𝑊 (𝑥
′
→ 𝑥)
简单起见可以取 𝑇 (𝑥 → 𝑥
′
) = 1, 那么
𝑊 (𝑥 → 𝑥
′
) =
1 𝑝(𝑥
′
) ≥ 𝑝(𝑥)
𝑝(𝑥
′
)
𝑝(𝑥)
𝑝(𝑥
′
) < 𝑝(𝑥)
那么就可得到 Metropolis 抽样的算法. 假定已经产生了序列 𝑥
1
, 𝑥
2
, · · · , 𝑥
𝑛
, 现在要产生 𝑥
𝑛+1
, 则可构造试
探解
𝑥
𝑡
= 𝑥
𝑛
+ (𝜉 − 0.5)Δ𝑥
其中 𝜉 是 [0, 1] 上的随机数,Δ𝑥 是固定步长, 计算比值
𝑟 =
𝑝(𝑥
𝑡
)
𝑝(𝑥
𝑛
)
分两种情况讨论
1. 若 𝑟 ≥ 1, 则接受 𝑥
𝑡
, 即 𝑥
𝑛+1
= 𝑥
𝑡
2. 若 𝑟 < 1, 则产生 [0, 1] 上的随机数 𝜉
′
, 若 𝜉
′
< 𝑟, 则接受 𝑥
𝑡
, 𝑥
𝑛+1
= 𝑥
𝑡
, 否则拒绝 𝑥
𝑡
, 𝑥
𝑛+1
= 𝑥
𝑛
这样抽样得到的序列显然两两是相关的, 但是对于积分计算而言, 并不关心这种相关性而只在意抽样点的
分布. 只要抽样点够多, 就能得到平衡分布
3 Metropolis-Hastings 抽样
为了使得分布收敛得更快, 转移矩阵 𝑇 (𝑥 → 𝑥
′
) 可以取为非对称的, 一般取为与目标分布相似的分布, 依
照细致平衡条件, 接受概率为
𝐴(𝑥 → 𝑥
′
) =
1 𝑝(𝑥
′
)𝑇 ( 𝑥
′
→ 𝑥) ≥ 𝑝(𝑥) 𝑇 (𝑥 → 𝑥
′
)
𝑝(𝑥
′
)𝑇 ( 𝑥
′
→ 𝑥)
𝑝(𝑥)𝑇 (𝑥 → 𝑥
′
)
𝑝(𝑥
′
)𝑇 ( 𝑥
′
→ 𝑥) < 𝑝(𝑥)𝑇 (𝑥 → 𝑥
′
)
那么概率矩阵 𝑊 就可以写为
𝑊 (𝑥 → 𝑥
′
) =
𝑇 (𝑥 → 𝑥
′
) 𝑝(𝑥
′
)𝑇 ( 𝑥
′
→ 𝑥) ≥ 𝑝(𝑥)𝑇 (𝑥 → 𝑥
′
)
𝑝(𝑥
′
)𝑇 ( 𝑥
′
→ 𝑥)
𝑝(𝑥)
𝑝(𝑥
′
)𝑇 ( 𝑥
′
→ 𝑥) < 𝑝(𝑥)𝑇 (𝑥 → 𝑥
′
)
