MCMC 通过构建马尔可夫链使其收敛到目标分布，包括拒绝采样、重要性采样、Metropolis-Hastings 和 Gibbs 采样。

采样方法对比

拒绝采样

提议分布 $q(z)$ 满足 $Mq(z)\ge p(z)$，接受率：

$$\alpha=\frac{p(z)}{Mq(z)}\le 1$$

重要性采样

$$\mathbb{E}{p(z)}[f(z)]=\frac{1}{N}\sum{i=1}^Nf(z_i)\frac{p(z_i)}{q(z_i)}$$

权重过小时效率低。

马尔可夫链

平稳分布满足：

$$\pi(x)p_{x\to x^}=\pi(x^)p_{x^*\to x}$$

Metropolis-Hastings 算法

接受率：

$$\alpha(z,z^)=\min\left{1,\frac{p(z^)Q_{z^\to z}}{p(z)Q_{z\to z^}}\right}$$

算法流程：

1. 均匀采样 $u\in[0,1]$
2. 生成 $z^\sim Q(z^|z^{i-1})$
3. 计算 $\alpha$
4. 若 $\alpha\ge u$，则 $z^i=z^*$，否则 $z^i=z^{i-1}$

Gibbs 采样

固定其他维度，采样单个维度：

$$z_i^{t+1}\sim p(z_i|z_{-i})$$

Gibbs 采样是 MH 采样的特例，接受率恒为 1。

MCMC 问题