马尔科夫链蒙特卡洛法适合于随机变量是多元的、密度函数是非标准形式的随机变量各分量不独立的情况。如何构建具体的马尔科夫链是这个方法的关键，离散变量的时候，需要定义转移矩阵，构建可逆马尔科夫链，保证遍历定理成立。常用的马尔科夫链蒙特卡洛法有Metropolis-Hasting算法，吉布斯抽样。

1 基本步骤

1）首先，在随机变量x的状态空间S上构造一个满足遍历定理的马尔科夫链，使其平稳分布为目标分布p(x);

2）从状态空间的某一点x0出发，用构造的马尔科夫链进行随机游走，产生样本序列x0,x1,x2..,xt,..。

3）应用马尔科夫链遍历定理，确定正整数m、n，得到样本集合求得函数f(x)的均值（遍历均值）

       满足遍历定理的马尔科夫链时间趋于无穷时马尔科夫链的状态分布趋于平稳分布，随机变量的函数的样本均值以概率1收敛于该函数的数学期望

Metropolis-Hastings算法

1 基本原理

1.1 马尔科夫链

假设要抽样的概率分布为p(x)，MH算法采用转移核为p(x,x')的马尔科夫链：

其中q(x,x')和a(x,x')分别称为建议分布和接受分布，建议分布为另一个马尔科夫链的转移核，而接受分布a(x,x')是

如果在时刻(t-1)处于状态x，即xt-1=x，则先按照建议分布q(x,x')抽样产生一个候选状态x’，然后按照接受分布a(x,x')抽样决定是否接受状态x',以概率a(x,x')决定接受x'，时刻t状态转移到x’，以概率（1-a(x,x')）拒绝x’，决定时刻t仍停留在状态x，

也就是说从（0,1）上的均匀分布中抽取一个随机数u，决定t时刻的状态。

1.2 建议分布

介绍两种建议分布q(x,x')的常用形式。

第一种形式，假设分布是对称的，即对任意的x和x’有q(x,x')=q(x',x)，这样的建议分布称为Metropolis选择，Metropolis选择的特点是当x'与x接近时，q(x,x')的概率值高，否则q(x,x')的概率值低。状态转移在附近点的可能性更大。

第二种形式称为独立抽样，假设建议分布q(x,x')与当前状态无关即q(x,x')=q(x')。建议分布的计算按照q(x')独立抽样进行，独立抽样实现简单，但收敛速度较慢，通常选择接近目标分布p(x)的分布作为建议分布

1.3 算法步骤

输入;抽样的目标分布的密度函数p(x)，函数f(x)；

输出：p(x)的随机样本，函数样本均值fmn；

参数：收敛步数m，迭代步数n。

1）任意选择一个初始值x0

2）对i=1到n执行循环

     （a）设状态，按照建议分布q(x,x')随机选取候选状态x’

     （b）计算接受概率

     （c）从区间（0，1）中按均匀分布随机抽取一个数u。若，则状态xi=x’；否则状态 xi=x。

3）得到样本集合。计算