问题目标
对于任意给定的目标分布$\pi(x)$， 我们如何找到以它为唯一平稳分布的马尔科夫链， 并且基于马尔科夫链采样的方法， 实现对其的近似采样。
要找到这么一个马尔科夫链， 本质上就是要找到它的转移概率矩阵P， 那么首先确立一个思考路径： 有没有什么条件， 使得只要我们的转移矩阵P满足了， 就意味着目标分布$\pi(x)$就是转移矩阵P对应的马尔科夫链的平稳分布呢？
这个条件就是马尔科夫链的细致平稳条件。
平稳分布判定： 细致平稳条件
设有马尔科夫链$X$， 状态空间$S$， 转移概率矩阵为$P$， 以及我们关注的状态分布$\pi = (\pi_1, \pi_2, \pi_3, …)$， 对于任意时刻$t$都满足: $\pi_ip_{ij} = \pi_jp_{ji}$， 则称状态分布$\pi$满足马尔科夫链的细致平衡条件， 则称状态分布$\pi$满足马尔科夫链的细致平衡条件， 该状态分布$\pi$就是马尔科夫链$X$的平稳分布。
证明：
如果$\pi_ip_{ij} = \pi_jp_{ji}$， 我们同时对两边的等式求和：
\[\sum_i \pi_i p_{ij} = \sum_i \pi_j p_{ji}\]显然也是成立的。
观察等式的右边， $\pi_j$的取值是独立于参数$i$的， 可以提出来：
\[\sum_i \pi_j p_{ji} = \pi_j \sum_i p_{ji}\]同时一句马尔科夫状态转移矩阵的归一性， 可知$\sum_i p_{ji} = 1$， 因此归结起来就有：
\[\sum_i \pi_i p_{ij} = \sum_{i}\pi_j p_{ji} = \pi_j \sum_i p_{ji} = \pi_j\]证毕。
wtf？？？
对于每一个j的具体取值， $\sum_i \pi_i p_{ij} = \pi_j$的计算过程实际上就是依状态分布（行向量）与状态转移矩阵第j列（列向量）点乘的过程， 得到的是一个数值， 值恰好是状态分布（行向量）的第j个元素， 那么如果让j取遍每一个索引值， 那么最终得到的就是：
\[\sum_i \pi_i p_{i1} = \pi_1 \\ \sum_i \pi_i p_{i2} = \pi_2 \\ \sum_i \pi_i p_{i3} = \pi_3 \\ \cdots \\ \sum_i \pi_i p_{iN} = \pi_N\]用一个式子综合起来就是：
\[\pi P = \pi\]这正是平稳分布的定义式， 这说明了， 满足细致平稳分布条件的目标分布$\pi$就是以矩阵P为状态转移矩阵的马尔科夫链的平稳分布。
如果此时这个转移概率矩阵对应的马尔科夫链满足不可约、非周期和正常返， 那么进一步说明该状态分布$\pi$是马尔科夫链的唯一平稳分布。
当然如果找到了这个转移矩阵P， 一般而言都是满足这个条件的。
因此， 一旦找到了状态转移矩阵， 就确定了马尔科夫链。
但是我们随便找一个状态转移矩阵Q， 一般是无法满足细致平稳条件的：
\[\pi(i)Q(i, j) \neq \pi(j)Q(j, i)\]对于$Q(i, j)$， 离散型马尔科夫链时， 我们称之为转移概率， 连续性马尔科夫链我们称之为转移概率密度， 或称转移核。
Metropolis-Hastings采样方法
在这个采样方法中， 针对每一个转移概率$Q(i, j)$， 我们再定义一个接受概率$\alpha(i, j)$， 使得每一个我们最终要构造的状态转移矩阵中的每一项$P(i, j)$都是$Q(i, j)$和$\alpha(i, j)$相乘的结果。
即目标马尔科夫矩阵的状态转移矩阵中的每一项都满足：
\[P(i, j) = Q(i, j)\alpha(i, j)\]再建议马尔科夫链中，从状态i转移到状态j的概率是$Q(i, j)$， 而在目标马尔科夫链中，从状态i到状态j的转移概率是$Q(i, j)\alpha(i, j)$， $\alpha(i, j)$表示一个接受概率， 它满足$\alpha(i, j) \leq 1$, 相比于建议马尔科夫链， 再目标马尔科夫链中，从状态i到状态j的转移概率都减小了， 但是马尔科夫链的概率转移矩阵要满足$\sum_j P(i, j) = 1$， 所有的$P(i, j)$， $P(i, i)$增大了。
我们要找的目标是状态转移概率矩阵P， 它的唯一稳态时目标分布$\pi(x)$， 我们参考上一篇接受——拒绝采样方法的思想精髓： 既然这个P矩阵难找， 我们能不能也找一个虽未的“建议矩阵Q”， 这个Q满足任意性， 这样我们能够利用一个明确的、便于随机游走的马尔科夫链， 基于转移概率的建议矩阵Q中的每一个具体项$Q(i, j)$以及接受概率$\alpha(i, j)$来共同决定最终从状态i到状态j的状态转移概率。
原本要找一个转移状态概率P， 满足细致平稳条件：
\[\pi(i)P(i. j) = \pi(j) P(j, i)\]而现在则是再建议转移概率矩阵Q可以任选的前提下， 找到一个接受概率$\alpha(i, j)$， 替换掉$P(i, j) = Q(i, j)\alpha(i, j)$， 满足下面的等式成立：
\[\pi(i)Q(i, j)\alpha(i, j) = \pi(j)Q(j, i)\alpha(j, i)\]对于任意给定的建议转移概率矩阵Q， 这个接受概率$\alpha$都一定存在吗？ 答案是：一定存在。 马尔科夫链蒙特卡罗方法中的Metropolis-Hastings采样中明确了接受概率$\alpha$的表达式：
\[\alpha(i, j) = min(\frac{\pi(j)Q(j, i)}{\pi(i)Q(i, j)}, 1)\]也就是说我们任选一个建议矩阵Q， 那么由这个矩阵的每一项和对应的接受概率相乘：
\[Q(i, j)\alpha(i, j) = Q(i, j)min(\frac{\pi(j)Q(j, i)}{\pi(i)Q(i, j)}, 1)\]用这所有相乘得到的结果所对应构成的新矩阵， 就是目标分布$\pi$为唯一稳态分布的马尔科夫链的转移概率矩阵P。
M-H采样方法的严格证明
\[P(i, j) = Q(i, j)\alpha(i, j) = Q(i, j)min(\frac{\pi(j)Q(j, i)}{\pi(i)Q(i, j)}, 1)\]当$\frac{\pi(j)Q(j, i)}{\pi(i)Q(i, j)} \geq 1$， 即$\pi(j)Q(j, i) \geq \pi(i)Q(i, j)$时， 有：
\[\alpha(i, j) = 1, P(i, j) = Q(i, j)\]当$\frac{\pi(j)Q(j, i)}{\pi(i)Q(i, j)} < 1$， 即$\pi(j)Q(j, i) < \pi(i)Q(i, j)$时， 有：
\[\alpha(i, j) = \frac{\pi(j)Q(j, i)}{\pi(i)Q(i, j)}, P(i, j) = Q(j, i)\frac{\pi(j)}{\pi(i)}\]总结起来就是：
- 当$\pi(j)Q(j, i) \geq \pi(i)Q(i, j)$， $P(i, j) = Q(i, j)$
- 当$\pi(j)Q(j, i) < \pi(i)Q(i, j)$， $P(i, j) = Q(j, i)\frac{\pi(j)}{\pi(i)}$
我们再来推导$Q(i, j)\alpha(i, j)$是否满足细致平稳条件：
\[\pi(i)P(i, j) = \pi(i)Q(i, j)\alpha(i, j) = \pi(i)Q(i, j)min(\frac{\pi(j)Q(j, i)}{\pi(i)Q(i, j)}, 1) \\ = min(\pi(j)Q(j, i), \pi(i)Q(i, j)) = \pi(j)Q(j, i)min(1, \frac{\pi(i)Q(i, j)}{\pi(j)Q(j, i)})\]接下来只需要证明：
\[\pi(j)P(j, i) = \pi(j)Q(j, i)min(1, \frac{\pi(i)Q(i, j)}{\pi(j)Q(j, i)})\]再简化一点， 就是证明：
\[P(j, i) = Q(j, i)min(1, \frac{\pi(i)Q(i, j)}{\pi(j)Q(j, i)})\]