学步园

随着计算机技术的快速发展和统计方法的不断丰富，产生了广泛应用的统计计算方法，例如EM算法、Bootstrap方法、MCMC方法等。这些方法大多涉及到随机抽样，即需要产生满足某分布的随机数。通常这些随机数产生是借助计算机实现，实际上是伪随机数。

(1)最简单的也是万能的随机数产生方法Inverse CDF Method

设随机变量X的分布函数为F(x)，令，如果U~U(0,1)，那么的分布就为F(x)。证明很简单

所以总的来说Inverse CDF Method的具体过称为，虽然这个方法有理论基础，但是对于复杂度函数求逆函数太难了！！！

（2）Acceptance/Rejection Methods

这个方法好像是大牛美男子冯诺依曼提出来的，这个证明比较复杂一点，我写下来：

至此我们证明了这个方法的正确性，同时我们应该注意这里面的c值是大于1的数，并且有很重要的意义：c表示成功产生随机样本所需要的平均次数！所以为了提高采样效率，通常要求c尽可能的取得小一点。c越小效率越高。这个方法虽然很漂亮，但是对于高维的分布，想找到一个合适的majorizing
function 太困难了！！！

（3）基于Markov链的随机抽样方法

假设大家对Markov链的性质比较了解，不了解可以随便找一本随机过程的书来看。这里用到的是不可约非周期时间可逆的马氏链。这是一类性质很好的马氏链。

我们引入了一个新的随机变量Y，看似把问题搞复杂了其实不然，正是根据马氏链的性质我们才更好的解决了这个问题，其中的转移核非常重要，可以把它理解为一步转移概率。根据时间可逆马氏链的性质，如果，那么就是该链的平稳分布（归一化之后）。我们可以证明刚才构造的链正好满足这个要求。

所以f(x)正好是该链的极限分布（只看x，不管y）。基于Markov链的方式产生随机样本，通常需要一个长时间的转移后才认为服从所需分布，这段过程称为burn in过程。burn in过程产生的样本是没用的，扔掉。同时到达了平稳分布之后，产生的是不独立同分布的样本。如果希望产生iid样本，一般可以用多链方法，或者每隔H（H足够大，越大可以认为相关性越小）个采一个点。目前最流行的基于Markov链产生随机数的算法为Metropolis
Hastings算法。由Metropolis1953年提出并由Hastings1970年加以推广，有时间接着写。。。