详解Markov Chain Monte Carlo (MCMC)
MCMC的本质是通过Markov Chain的stationary distribution(平稳分布)来指导随机采样的一种方法。说到MCMC， 首先要先了解什么是Monte Carlo和Markov Chain。
1. Monte Carlo (蒙特卡罗方法):
蒙特卡罗方法是指通过构造符合一定规则的随机数来解决数学上的各种问题，本质是根据采样来做估计期望(estimate expected value by sampling)，用公式表达：
就是根据x的分布p(x)来采样，并估算f(x)的期望.
具体步骤是
举个例子：如何用Monte Carlo来计算圆周率
我们选取一个大小的正方形，并在上面画1/4的圆。在这个正方形上根据uniform distribution来随机生成N个点，根据点的xy坐标即可计算出点到原点的距离（小于1在园内，大于1在圆外），如下图所示，圆内的点的数量与总的点数量之比即为
。
2. 蒙特卡罗积分：对被积函数变量区间进行随机均匀抽样，然后对抽样点的函数值求平均，从而可以得到函数积分的近似值。
对函数f(x)的积分公式为 , N 代表sample点的个数；
是sample
的概率密度函数，如果在区间[a,b] uniform sample，
尤其当f(x)的表达式未知时或难以直接计算其积分，我们可以采用蒙特卡罗积分来近似模拟出f(x)的积分。
MCMC是使用马尔可夫链的蒙特卡罗方法。其思想是计算马尔可夫链的平稳分布(stationary distribution)，并当作p(x)来进行sample的方法。
3.1 平稳分布(stationary distribution)
我们先来定义一下要涉及到的概念：
- 马尔可夫链:
- set of states: S
- 马尔可夫转移矩阵: P
- 平稳分布(stationary distribution)：
若Markov chain 满足：
- irreducibility,
- positive recurrence,
- aperiodicity.
则存在limiting distribution
上面的关于markov chain的三种性质讲起来又是3篇文章，这里就不多说了，感兴趣的同学可以自己看看，以后有时间我也会把这部分补上的。
limiting distribution不与起始位置相关，描述的是当我们对一个马尔可夫链进行无数次转移操作后，最后落在state j上的概率，并且这个概率是, 这里
是mean return time，表示从state j出发并最终回到state j的平均概率。
把每个state的综合起来就可以得到stationary distribution
, 并且存在性质
. 对google page rank有了解的同学会发现这里的stationary distribution其实和The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google 里面计算的eigen vector是一回事。
3.2 Metropolis Hasting方法
铺垫了这么多，我们终于可以来讲MCMC的具体方法了:
for k = 1,2,3...
- Sample x' from a wrong transition
- Accept proposal
with probability
- Otherwise stay at
是自己定义的transition function，，不需要等于真实的transition P。
以上就是MCMC的大致方法。