0.引子
书接前文，在
采样方法（一）
中我们讲到了拒绝采样、重要性采样一系列的
蒙特卡洛采样方法
，但这些方法在高维空间时都会遇到一些问题，因为很难找到非常合适的可采样Q分布，同时保证采样
效率
以及
精准度
。
本文将会介绍采样方法中最重要的一族算法，
MCMC（Markov Chain Monte Carlo）
，在之前我们的蒙特卡洛模拟都是按照如下公式进行的：
E [ f ( x ) ] ≈ 1 m ∑ i = 1 m f ( x i ) . x i ∼ p . i i d {E}[f(x)] \approx \frac{1}{m}\sum_{i=1}^m{f(x_i)}.\ \ x_i \sim p.iid
E
[
f
(
x
)
]
≈
m
1
i
=
1
∑
m
f
(
x
i
)
.
x
i
∼
p
.
i
i
d
我们的x都是独立采样出来的，而在MCMC中，它变成了
E [ f ( x ) ] ≈ 1 m ∑ i = 1 m f ( x i ) . ( x 0 , x 1 , . . . , x m ) ∼ M C ( p ) {E}[f(x)] \approx \frac{1}{m}\sum_{i=1}^m{f(x_i)}.\ \ (x_0,x_1,…,x_m)\sim MC(p)
E
[
f
(
x
)
]
≈
m
1
i
=
1
∑
m
f
(
x
i
)
.
(
x
0
,
x
1
,
.
.
.
,
x
m
)
∼
M
C
(
p
)
其中的
M C ( p ) MC(p)
M
C
(
p
)
就是我们本文的主角之一，
马尔可夫过程
（Markov Process）生成的
马尔可夫链
（Markov Chain）。
1.Markov Chain（马尔可夫链）
在
序列的算法（一·a）马尔可夫模型
中我们就说到了马尔可夫模型的马尔可夫链，简单来说就是满足
马尔可夫假设
P ( s n ∣ s 0 , s 1 , . . . , s n − 1 ) = P ( s n ∣ s n − 1 ) P(s_n|s_0,s_1,…,s_{n-1}) = P(s_n|s_{n-1})
P
(
s
n
∣
s
0
,
s
1
,
.
.
.
,
s
n
−
1
)
=
P
(
s
n
∣
s
n
−
1
)
的状态序列，由马尔可夫过程（Markov Process）生成。
一个
马尔可夫过程
由两部分组成，一是状态集合
Ω \Omega
Ω
,二是转移概率矩阵
T T
T
。
其流程是：选择一个初始的状态分布
π 0 \pi_0
π
0
，然后进行状态的转移：
π n = π n − 1 T \pi_n = \pi_{n-1}T
π
n
=
π
n
−
1
T
得到的
π 0 , π 1 , π 2 . . . π n \pi_0,\pi_1,\pi_2…\pi_n
π
0
,
π
1
,
π
2
.
.
.
π
n
状态分布序列。
注意：我们在这里讲的理论和推导都是基于离散变量的，但其实是可以直接推广到连续变量
。
马尔可夫链在很多场景都有应用，比如大名鼎鼎的pagerank算法，都用到了类似的转移过程；
马尔可夫链在某种特定情况下，有一个奇妙的性质：
在某种条件下，当你从一个分布
π 0 \pi_0
π
0
开始进行概率转移，无论你一开始
π 0 \pi_0
π
0
的选择是什么，最终会
收敛
到一个固定的分布
π \pi
π
，叫做稳态（steady-state）。
稳态满足条件：
π = π T \pi = \pi T
π
=
π
T
这里可以参考《LDA数学八卦0.4.2》的例子，非常生动地描述了社会阶层转化的一个例子，也对MCMC作了非常好的讲解
书归正传，回到我们采样的场景，我们知道，采样的难点就在于
概率密度函数
过于复杂而无法进行有效采样，如果我们可以
设计
一个马尔可夫过程，使得它最终
收敛
的分布是我们想要采样的概率分布，不就可以解决我们的问题了么。
前面提到了
在某种特定情况下
，这就是所有MCMC算法的理论基础
Ergodic Theorem
：
如果一个离散马尔可夫链
( x 0 , x 1 . . . x m ) (x_0,x_1…x_m)
(
x
0
,
x
1
.
.
.
x
m
)
是一个与时间无关的Irreducible的离散，并且有一个稳态分布
π \pi
π
,则：
E [ f ( x ) ] ≈ 1 m ∑ i = 1 m f ( x i ) . x ∼ π {E}[f(x)] \approx \frac{1}{m}\sum_{i=1}^m{f(x_i)}.\ \ x\sim \pi