马尔可夫蒙特卡洛（MCMC）

某一时刻状态转移概率只依赖于前一个状态

与初始的概率分布无关，马尔可夫链在有限次转移之后总能收敛到一个稳定的概率分布，称为平稳分布。公式表达： π ( j ) = ∑ i = 0 ∞ π ( i ) P i j \pi(j)=\sum_{i=0}^{\infty} \pi(i) P_{i j} π(j)=i=0∑∞​π(i)Pij​ 其中: π = [ π ( 1 ) , π ( 2 ) , … , π ( j ) , … ] 是 某 一 时 刻 的 概 率 分 布 ∑ i = 0 ∞ π ( i ) = 1 P i j = P ( X t + 1 = j ∣ X t = i ) 代 表 状 态 转 移 矩 阵 的 一 个 元 素 \pi=[\pi(1), \pi(2), \ldots, \pi(j), \ldots] 是某一时刻的概率分布 \\ \sum_{i=0}^{\infty} \pi(i)=1 \\P_{ij} = P(X_{t+1}=j \mid X_t = i) 代表状态转移矩阵的一个元素 π=[π(1),π(2),…,π(j),…]是某一时刻的概率分布i=0∑∞​π(i)=1Pij​=P(Xt+1​=j∣Xt​=i)代表状态转移矩阵的一个元素 一个包含三个状态的马尔可夫链的平稳分布可以是：[ 0.625 0.3125 0.0625]

马尔可夫链的平稳分布就可以看作我们要采样的样本集，可以通过状态转移矩阵得到

假定我们可以得到我们需要采样样本的平稳分布所对应的马尔科夫链状态转移矩阵，那么我们就可以用马尔科夫链采样得到我们需要的样本集，进而进行蒙特卡罗模拟。目前的问题是如何基于一个平稳分布求得状态转移矩阵。

先看细致平衡条件：如果非周期马尔科夫链的状态转移矩阵 P P P 和概率分布 π ( x ) \pi(x) π(x) 对于所有的 i , j i, j i,j 满足： π ( i ) P ( i , j ) = π ( j ) P ( j , i ) \pi(i) P(i, j)=\pi(j) P(j, i) π(i)P(i,j)=π(j)P(j,i) 则称概率分布 π ( x ) \pi(x) π(x) 是状态转移矩阵 P P P 的平稳分布。 证明很简单,由细致平稳条件有： ∑ i = 1 ∞ π ( i ) P ( i , j ) = ∑ i = 1 ∞ π ( j ) P ( j , i ) = π ( j ) ∑ i = 1 ∞ P ( j , i ) = π ( j ) \sum_{i=1}^{\infty} \pi(i) P(i, j)=\sum_{i=1}^{\infty} \pi(j) P(j, i)=\pi(j) \sum_{i=1}^{\infty} P(j, i)=\pi(j) i=1∑∞​π(i)P(i,j)=i=1∑∞​π(j)P(j,i)=π(j)i=1∑∞​P(j,i)=π(j) 将上式用矩阵表示即为： π P = π \pi P=\pi πP=π 只要找到可以使概率分布 π ( x ) \pi(x) π(x) 满足细致平稳分布的矩阵 P P P 即可从平稳分布 π \pi π, 找到对应的马尔科夫链状态转移矩阵 P P P 不过不幸的是，目标平稳分布是 π ( x ) \pi(x) π(x),随机找一个马尔科夫链状态转移矩阵 Q Q Q, 它很难满足细致平稳条件，即： π ( i ) Q ( i , j ) ≠ π ( j ) Q ( j , i ) \pi(i) Q(i, j) \neq \pi(j) Q(j, i) π(i)Q(i,j)​=π(j)Q(j,i)

为了让 π ( x ) 和 Q \pi(x)和Q π(x)和Q满足细致平衡条件，这时需要引入接受率 a ( i , j ) a(i,j) a(i,j)，使得下式成立 π ( i ) Q ( i , j ) α ( i , j ) = π ( j ) Q ( j , i ) α ( j , i ) \pi(i) Q(i, j) \alpha(i,j) = \pi(j) Q(j, i) \alpha(j,i) π(i)Q(i,j)α(i,j)=π(j)Q(j,i)α(j,i) α ( i , j ) = min ⁡ ( π ( j ) Q ( j , i ) π ( i ) Q ( i , j ) , 1 ) \alpha(i,j) = \min({\frac{\pi(j) Q(j, i) }{ \pi(i) Q(i, j)}, 1}) α(i,j)=min(π(i)Q(i,j)π(j)Q(j,i)​,1)