蒙特卡罗法也称统计模拟方法，是通过从概率模型的随机抽样进行近似数值计算的方法。
马尔可夫链蒙特卡罗法是以马尔可夫链为概率模型的蒙特卡罗法。
马尔可夫链蒙特卡罗法构建一个马尔可夫链，使其平稳分布就是要进行抽样的分布，首先基于该马尔可夫链进行随机游走，产生样本的序列，之后使用该平稳分布的样本进行近似数值计算。
Metropolis-Hastings算法是最基本的马尔可夫链蒙特卡罗法。
吉布斯抽样是更简单、使用更广泛的马尔可夫链蒙特卡罗法。
马尔可夫链蒙特卡罗法被应用于概率分布的估计、定积分的近似计算、最优化问题的近似求解等问题，特别是被应用于统计学习中概率模型的学习与推理，是重要的统计学习计算方法。
一、蒙特卡罗法
1、随机抽样
蒙特卡罗法要解决的问题是：
假设概率分布的定义已知，通过抽样获得概率分布的随机样本，并通过得到的随机样本对概率分布的特征进行分析。
比如：
从样本得到经验分布，从而估计总体分布。
或者从样本计算出样本均值，从而估计总体期望。
所以蒙特卡罗法的核心是随机抽样。
蒙特卡罗法
- 直接抽样法
- 接收-拒绝抽样法
- 重要性抽样法
接收-拒绝抽样法，重要性抽样法适合于概率密度函数复杂（如密度函数含有多个变量，各变量相互不独立，密度函数形式复杂），不能直接抽样的情况。
接收-拒绝抽样法
接收-拒绝法优点：容易实现，缺点是效率可能不高。
如果p(x)的涵盖体积占cq(x)的涵盖体积的比例很低，就会导致拒绝的比例很高，抽样效率很低。
注意：p(x)与cq(x)很接近，两者涵盖体积的差异也可能很大。
2、数学期望估计
一般的蒙特卡罗法也可用于数学期望估计。
3、积分计算
一般的蒙特卡罗法也可用于定积分的近似计算，称为蒙特卡罗积分。
二、马尔可夫链
1、基本定义
2、离散状态马尔可夫链
（1）转移概率矩阵和状态分布
转移概率矩阵
状态分布
有限离散状态的马尔可夫链可以由有向图表示
结点表示状态，边表示状态之间的转移，边上的数组表示转移概率。
从一个初始状态出发，根据有向边上定义的概率在状态之间随机跳转（或随机转移），就可以产生状态的序列。
马尔可夫链实际上是刻画随时间在状态之间转移的模型，假设未来的转移状态只有依赖于现在的状态，而与过去的状态无关。
2、平稳分布
直观上，如果马尔可夫链的平稳分布存在，那么以该平稳分布作为初始分布，面向未来进行随机状态转移，之后任何一个时刻的状态分布都是该平稳分布
3、连续状态马尔可夫链
4、马尔可夫链性质
（1）不可约
直观上，一个不可约的马尔可夫链，从任意状态出发，当经过充分长时间后，可以到达任意状态
（2）非周期
直观上，一个非周期性的马尔可夫链，不存在一个状态，从这一个状态出发，再返回到这个状态时所经历的时间长呈一定的周期性
（3）正常返
直观上，一个正常返的马尔可夫链，其中任意一个状态，从其他任意一个状态出发，当时间趋于无穷时，首次转移到这个状态的概率不为0。
（4）遍历定理
遍历定理的直观解释：
满足相应条件的马尔可夫链，当时间趋于无穷时，马尔可夫链的状态分布趋近于平稳分布，随机变量的函数的样本均值以概率1收敛于该函数的数学期望。
样本均值可以认为是时间均值，二数学期望是空间均值。遍历定理实际表述了遍历性的含义：当时间趋于无穷时，时间均值等于空间均值。
遍历定理的三个条件：不可约，非周期，正常返，保证了当时间趋于无穷时达到任意一个状态的概率不为0。
遍历均值
（5）可逆马尔可夫链
直观上，如果有可逆的马尔可夫链，那么以该马尔可夫链的平稳分布作为初始分布，进行随机状态转移，无论是面向未来还是面向过去，任何一个时刻的状态分布都是该平稳分布。
细致平衡方程
三、马尔可夫链蒙特卡罗法
1、基本想法
马尔可夫链蒙特卡罗法更合适于随机变量是多元的、密度函数是非标准形式的、随机变量各分量不独立等情况。
马尔可夫链蒙特卡罗法的基本想法：
构建具体的马尔可夫链：
- 连续变量的时候，需要定义转移核函数。
- 离散变量的时候，需要定义转移矩阵。
一个方法是定义特殊的转移核函数或者转移矩阵，构建可逆马尔可夫链，这样可以保证遍历定理成立。
常用的马尔可夫链蒙特卡罗法有Metropolis-Hastings算法，吉布斯抽样。
由于这个马尔可夫链满足遍历定理，随机游走的起始点并不影响得到的结果，即从不同的起始点出发，都会收敛到同一平稳分布。
马尔可夫链蒙特卡罗法的收敛性的判断通常是经验性的。
比如在马尔可夫链上进行随机游走，检验遍历均值是否收敛。具体地，每隔一段时间取一次样本，得到多个样本以后，计算遍历均值。
再比如，在马尔可夫链上并行进行多个随机游走，比较各个随机游走的遍历均值是否接近一致。
马尔科夫链蒙特卡罗法中得到的样本序列，相邻的样本是相关的，而不是独立的。
因此，在需要独立样本时，可以在该样本序列中再次进行随机抽样。
比如，每隔一段时间取一次样本，将主要得到的子样本集合作为独立样本集合。
马尔可夫链蒙特卡罗法比接受-拒绝法更容易实现，因为只需要定义马尔可夫链，而不需要定义建议分布。
一般来说马尔可夫链蒙特卡罗法比接受-拒绝法效率更高，没有大量被拒绝的样本，虽然燃烧期的样本也要抛弃。
2、基本步骤
可以将马尔可夫链蒙特卡罗法概括为以下三步。
3、马尔可夫链蒙特卡罗法与统计学习
贝叶斯学习中经常需要进行三种积分运算：
- 归范化
- 边缘化
- 数学期望
马尔可夫链蒙特卡罗法为这些计算提供了一个通用的有效解决方案。
四、Metropolis-Hastings算法
1、基本原理
（1）马尔可夫链
定理
（2）建议分部
两种常用形式：
（3）满条件分部
2、Metropolis-Hastings算法
3、单分量Metropolis-Hastings算法
在Metropolis-Hastings算法中，通常需要对多元变量分布进行抽样，有时对多元变量分布的抽样是困难的。
可以对多元变量的每一变量的条件分布依次分别进行抽样，从而实现对整个多元变量的一次抽样，这就是单分量Metropolis-Hastings算法。
五、吉布斯抽样
吉布斯抽样是马尔可夫链蒙特卡罗法的常用算法。可认为是Metropolis-Hastings算法的特殊情况，但是更容易实现，因而被广泛使用。
1、基本原理
吉布斯抽样用于多元变量联合分布的抽样和估计。
基本做法：从联合概率分布定义满条件概率分布，依次对满条件概率分布进行抽样，得到样本的序列。
可以证明这样的抽样过程是在一个马尔可夫链上的随机游走，每一个样本对应着马尔可夫链的状态，平稳分布就是目标的联合分布。
整体成为一个马尔可夫链蒙特卡罗法，燃烧期之后的样本就是联合分布的随机样本。
吉布斯抽样是单分量Metropolis-Hastings算法的特殊情况。
2、吉布斯抽样算法
单分量Metropolis-Hastings算法
- 抽样会在样本点之间移动，但其间可能在某一些样本点上停留（由于抽样被拒绝）
- 适合于满条件概率分布不容易抽样的情况，使用容易抽样的条件分布作建议分布。
吉布斯抽样算法
- 抽样会在样本点之间持续移动
- 适合于满条件概率分布容易抽样的情况。
3、抽样计算
吉布斯抽样中需要对满条件概率分布进行重复多次抽样。可以利用概率分布的性质提供抽样的效率。
以贝叶斯学习为例介绍这个技巧
