马尔可夫蒙特卡洛采样法

可以用于比较复杂的分布的采样，并且在高维空间中也能使用
马尔可夫蒙特卡洛法
- 蒙特卡洛法：基于采样的数值型近似求解方法
- 马尔可夫链：用于采样
MCMC基本思想
- 针对目标分布，构造一个马尔可夫链，使得该马尔可夫链的平稳分布就是目标分布
- 从任何一个初始状态出发，沿着马尔可夫链进行转移
- 最终的状态转移序列会收敛到目标分布，得到一系列样本
核心点：构造马尔可夫链、确定状态转移序列

Metropolis-Hastings采样法

对于目标分布(p(x))，选择一个易采样的参考条件分布(q(x^*|x))，并令

[A(x, x^*) = mathop{min} {1, frac{p(x^*)q(x|x^*)}{p(x)q(x^*|x)} } ]

然后根据如下过程进行采样

随机选一个初始样本(x^{(0)})
For t = 1, 2, 3,,,,,,
- 根据参考条件分布(q(x^{*}|x^{(t-1)}))抽取一个样本(x^{*})
- 根据均匀分布(U(0,1))产生随机数(u)
- 若(u < A(x^{(t-1)}, x^*))，则令(x^{(t)} = x^*)，否则令(x^{(t)} = x^{(t-1)})
样本序列({ dots, x^{(t-1)}, x^{(t)} })最终会收敛到目标分布(p(x))
(A)就是转移概率，(x)之间构成马尔可夫链

Metropolis-Hastings算法的特例
核心思想：每次只对样本的一个维度进行采样和更新
对于目标分布(p(x))，其中(x=(x_1, cdots, x_d))是多维向量，按如下过程采样：
- 随机选择初始状态(x^{(0)}=(x_1^{(0)}, cdots, x_d^{(0)}))
- (For t = 1, 2, 3, cdots):
  - 对于前一步产生的样本(x^{(t-1)} = (x_1^{(t-1)},cdots, x_d^{(t-1)})),依次采样和更新每个维度的值，即依次随机抽取分量(x_1^{(t)} sim p(x_1|x_2^{(t-1)}, x_3^{(t-1)},dots,x_d^{(t-1)}),dots,p(x_d|x_1^{(t)}, x_2^{(t)},dots,x_{d-1}^{(t)}))
- 形成新的样本(x^{(t)} = (x_1^{(t)}, cdots, x_d^{(t)}))
每个维度的采样都是从以其他维度为条件的条件概率中采样的。该条件分布包含本轮已经采样的维度或者上轮采样的维度
每个维度的抽样和更新，可以是随机顺序