随机数产生,mcmc方法,em算法,bootstrap方法.doc

随机数产生,MCMC方法,EM算法,bootstrap方法
统计计算文献报告
摘要:本文主要围绕随机数的产生算法、MCMC算法、EM算法、Bootstrap算法四种统计计算方法,介绍各方法的算法原理;并针对每个算法给出了实例。
关键词:随机数,MCMC方法,EM算法,bootstrap方法
1. 随机数的产生
统计模拟的最基本问题是随机数生成,是按统计模型生成数据的基础。随机数生成可分成两类:[0,1]区间上均匀随机数生成和非均匀随机数生成,是随机数生成问题的两个基本研究领域[1]。
[0,1]区间上均匀随机数生成
[0,1]上均匀随机数生成是随机数生成之基础,非均匀随机数是由[0,1]上均匀随机数经相应运算而产生的。[0,1]上均匀随机数的质量决定了非均匀随机数的质量。如何快速地生成[0,1]上高质量均匀随机数是普遍关注的问题。生成方法分为两类:物理方法和数学方法[2]。
物理方法
基本原理为:利用某些物理现象,在计算机上增加些特殊设备,可以在计算机上直接产生随机数。这些特殊设备称为随机数发生器。把具有随机性质的物理过程变换为随机数,使用物理随机随机数发生器,在计算机上可以得到真正的随机数,其随机性和均匀性都是很好的、而且是取之不尽用之不竭的。但是用物理方法产生的随机数序列无法重复实现,不能进
行程序复算,给验证结果带来很大困难。而且,物理随机数发生器的稳定性经常需进行检查和维修,费用昂贵。因此,大大降低了这种方法的使用价值[3]。
数学方法
在计算机上用数学方法产生均匀随机数是指按照一定的计算方法而产生的数列,它们具有类似于均匀随机变量的独立抽样序列的性质,这些数既然是依照确定算法产生的,便不可能是真正的随机数,因此常把用数学方法产生的随机数称为伪随机数。用数学方法在计算机上产生随机数是目前使用最广、发展很快的一类方法。他的特地啊是占用内存少、速度快又便于复算。
同余法
目前应用最广泛的随机数产生的方法是同余法。它是由Lehmer在1951年提出的。此方法利用数论中的同于运算来产生随机数,故称为同余发生器。它包括混合同余发生器和乘同于发生器。它是目前使用最普遍、发展迅速的产生随机数的数学方法。
基本方法如下:
?x1?ax0?b ?modm???xn??axn?1?c? ?modm? ()
?u?x/m n?1,2,?n?n
其中m为模数,a为乘子(乘数),c为增量(加数),且xn,m,a,c均为非负整数。u1,u2,?,uk就是k个[0,1]上的伪随机数。按()给出的为随机数生成方法称为线性同余法。当b?0时称为混合同余法,b?0时称
为乘同余法,当b?0且模是素数时,称为素数模乘同余法。线性同余法产生的随机数序列具有周期性,其最大周期为m。
著名的Coveyou与Macpherson混合同于发生器为:
1535??xn?5xn?1?1 mod(2) ?35??un?xn/2 n?1,2,?
Kobayashi混合同余器是
31??xn?314159269xn?1?453806245 mod(2) ?31??un?xn/2 n?1,2,?
非均匀随机数生成
非均匀随机数的生成是另一类随机数生成方法,是基于[0,1]上的均匀随机数产生给定概率密度函数的算法。如正态分布随机数发生器,指数分布随机数发生器等,可以利用分布的特殊性质,针对性极强。在一些实际问题或统计模拟时需要上万,几十万,甚至上百万个非均匀随机数。这时,算法的速度就显得十分重要。目前产生非聚云随机数的一般方法有:直接抽样法(反函数法)、变换抽样法、值序抽样法和舍选抽样法。下面针对反函数变换法和舍选法进行介绍。
反函数变换法
设随机变量X的分布函数是F(?),且F是连续的。那么,U?F(X)是随机变量,其分布是(0,1)上均匀分布。于是,有产生具有给定分布函数F(?)的非均匀随机数X的算法:
X=F?1(U),U~U(0 ,1)
这里U(0,1)是(0,1)上的均匀分布,F?1(?)是F的反函数。是一个通用算法,对任何连续分布函数的反函数变换法,简称反函数变换法。该方法的缺点是
:并不是任何分布函数都有快速算法。对常见分布,如正态分布,F分布等分布函数仅可以数值计算,没有解析表达式。
舍选法
舍选法是非常有用的随机数生成方法。其应用最为广泛,研究成果也最多。设f(?)是随机变量X的密度函数,如何生成有密度函数f(?)的随机数是随机数生成中最重要的和最基本的问题。最普遍应用的方法就是舍选法。方法如下:
(?)满足以下条件:
?
f(x