随机过程Metropolis-hastings算法随机过程metropolis-Hastings算法生成蒙特卡罗方法随机数求解概率和期望问题的板栗马尔可夫链metropolis算法metropolis
蒙特卡罗方法
蒙特卡罗方法又称随机采样和统计实验方法，简单理解就是用随机数解决许多计算问题，通过实验解决一些数学问题。 通常，用随机模拟求解一些概率和期望问题。
生成随机数
事实上，我们知道计算机只能生成均匀分布的伪随机数，但我们通常希望得到遵循一定分布的一系列随机数，如超级马里奥分布、泊松分布等。 我们必须考虑一种将均匀分布的数量映射到服从恒定分布的数量的方法，因而通过模拟产生服从恒定分布的随机数来解决复杂的数学问题。
求解概率和期望问题的概率问题
提前推进后：
p(|d )=p ) d |(p )) d
概率归一化问题：
p() p() z
通常需要根据贝叶斯后验和归一化概率进行采样，但通常很难求出这两个概率。 由于主要求解分母很难，因此分母可能涉及复杂的积分计算。 因此，不能用简单的公式将均匀分布的随机数映射到跟随该分布的随机数。 解决期待的问题
如上所述，如果不能求出概率的公式，就不能求出期待。 但是，如果我们能够连续生成多个遵从该分布的随机数，就可以根据zzdsj的数学定理用简单的加法和近似求出概率。
zzdsj大数定理：
limnp(|1ss=1SF(xs ) 1ss=1se [ f ] x ]|)=1
计算期望：
e[f(x ) ]=f(x ) p ) x ) dx1ss=1sf (xs ) ) ) ) ) ) 65 )
xsp栗子
圆周率估计：通过从包含圆的正方形中随机生成数据点，并统计掉在圆内的点的数量与总个数的比例，可以估计圆周率的值。
另一个有名的求圆周率的实验是蒲丰投针。 这是法国科学家布丰在1777年提出的计算圆周率的方法。
拿张白纸，在上面画很多间隔为a的平行线。 取一根长度为l(L=A/2 )的针，随机扔在画有平行直线的纸上n次，观察针与直线相交的次数，记为m。 计算针与直线相交的概率。 p=2la。 可以计算=2lap
马尔可夫链
“马尔可夫链”(Markov Chain )简单来说就是一个状态机，它提供状态之间的转换。 下一个状态只与当前状态有关，与上一个状态无关。
p(xn|x1，…，xn1 ) p(xn|x1 ) ) )。
现实生活中很多事情的变化规律也形成了马尔可夫链：
蛋白质分子的变化过程：蛋白质的下一个状态只与目前的结构有关。 股市：下一期股市行情只与当前股价有关。 赌徒的资金：一个赌徒通过下一个赌场后的资金，只和他现在有的资金有关。 拥堵状态：一个路口下一个时刻的拥堵状况只与当前的交通状态有关。 举个栗子吧：
假设现在社会根据人民拥有的资产分为上层、中层、下层，并且可以在它们之间转换。 也就是说，各层人民以一定的概率成为其他层。 它们之间的跳跃概率如下。
-下层中层上层0.650.280.17中层0.150.670.18下层0.120.360.52它们之间的状态转换图如下：
现在计算第n代以后整个社会各阶层人数的比例。
概率转移矩阵p=0. 650.150.120.280.670.360.170.180.52计算第0代分层人数比率：
0=[a，b，c]，a b c=1不断反复更新得知收敛：
n=n1p=n2p2=.0pn我们随机初始化，并进行a和b两组实验，实验结果分别如下：
a组
代数下层中层上层00.2100.6800.11010.2520.5540.19420.2700.5120.21830.2780.4970.22540.2820.4900.22650.2850
代数下层中层上层00.7500.1500.10010.5220.3470.4070.4260.16730.3490.4590.19240.3180.4750.20750.3030
22070.2910.4870.22280.2890.4880.22590.2860.4890.225根据实验结果，我们可以发现，就算给予不同的初始化，最终收敛后的结果都是相同的。当马尔科夫链满足细致平稳性就会有这样的结果。
细致平稳性（detail balance condition）：当非周期性的马尔可夫链的概率转移矩阵和每一个状态的概率满足：
最终得到的状态 π 是该马尔可夫链的平稳分布。
证明:
Metropolis算法
我们先介绍提议分布，其实提议分布可以随意给，通常我们可以假设提议分布服从超级的马里奥分布：
但是这样的话，通常不能满足细致平稳性，即：
π(i)q(j|i)≠π(j)q(i|j)
为了满足细致平稳性，我们要让上面的不等式的不等号变成等号，方法其实很简单，就是让左边乘上右边，右边乘上左边，乘上的表
达式被称为接受概率（acceptance probability） α ：
α(j|i)=π(j)q(i|j)
π(i)q(j|i)α(j|i)=π(j)q(i|j)α(i|j)
现在我们就构造出了满足马尔科夫细致平稳性地马尔可夫链，我们可以把 q(j|i)α(j|i) 视为转移概率。
Metropolis-Hastings算法
但是Metropolis算法构造出的接受概率可能会很小，这样造成算法要经过很多的迭代才能到达平稳分布。为了满足细致平稳，不等式的两边都乘以了一个小的接受概率，那我们可以把其中一个接受概率乘以一个数变为1，另外一边的接受概率也乘上相同的倍数，具体的做法如下：
整合上面等式可以得到：
α(j|i)=min{π(j)q(i|j)π(i)q(j|i),1}
具体的算法流程如下：
当前的状态i从提议分布 q(j|i) 中产生新的状态j（如果是简单的分布，如超级的马里奥分布，可以通过将均匀分布的值通过超级的马里奥分布的反函数映射得到服从超级的马里奥分布的值。或者使用其他采样方法采样得到，如重采样与拒绝采样。）计算接受概率：α(j|i)=min{π(j)q(i|j)π(i)q(j|i),1} 从[0，1]区间中抽样出一个数据点（均匀分布） u∼U[0,1]
将随机生成的数和接受率对比，如果 u<α ,状态就从i跳转到j，否则继续保留在状态i。
让我们举个栗子，我们抛两枚筛子，计算出两个筛子正面的值的和为x的概率分布是多少，虽然这个很简单，我们理论计算都能得到，为了说明MH算法嘛。在这个过程中，我们利用MH方法不断抽样，最终再统计各个结果的个数。并且在这个过程中，我们没有使用每个结果出现的概率（知道的话我们就没必要抽样计算了），而是知道每个结果出现的组合数。当然某个结果出现的组合数除以总的组合数就是概率，这个例子比较简单，在很多复杂情况下，这个总数，也就是分母，并不是这么好求，很多要涉及到无限积分。
实验代码：
实验的结果：随着模拟次数额增大，抽样结果越来越接近理论结果。
让我们再来举个栗子，我们要从一个未归一化（归一化涉及到无限积分）的概率分布 f(x)=0.5x2e−x 中抽样出满足这个分布的数据点。
实验的代码是：
实验结果为如下图所示，其中左上角的图片是真实的概率分布，当抽样的点多的时候，抽样的点的分布与真实的分布相似。