第五章 随机数的产生.doc

第五章 随机数的产生5.1 0, 1均分布随机数产生 1、0, 1均匀分布 密度函数 分布函数 2、产生均匀随机数的一般方法 （1）随机数表法 把事先作好的随机数输入到内存或外存贮器中 缺点：占用下量内存，放在外存贮器时，降低运行速度 （2）利用硬设备产生随机数，如放射粒子的放射源，电子管或晶体管的固有噪声放大作为随机源。 （3）用移位寄存器产生随机数， （4）用数学公式产生随机数 3、产生伪随机数的要求 （1）有较理想的随机性和均匀性 （2）程序应简短、运行快、占内存少 （3）循环周期应可能大 （4）伪随机数列中，前后之间和各子列之间，相互独立。 （5）保证所要求的精度 4、数学公式产生的方法 （1）平方取中法 b进制2k位的数，自乘后得到4k位的乘积，去头截位，取中间2k位，易出现退化现象 （2）倍积取中法 Si+1=k. Si，k为常数，k. Si表示k. Si中间的n位 （3）同余法a、加同余法统计性能差b、二次同余法计算复杂c、线性同余法5、线性同余法其中a为乘子，为种子，C为常数，M为模迭代步骤： （1）设定a, c, M值，并给定初始种子 （2）令 （3） （4） （5），转入（3）分析：，取整序列返回初始值之前取值的个数，称为序列的周期p，选择和M使p达到最大结论1：若，S为计算机位数，若c与M互素，且则的周期为M，p=M。结论2：若c=0即乘同余法（1）M=2S，a=4k+1或a=8k3, Xo为奇数（2）令M取（1，2S）中的最大素数，a是M原根，则乘同余法的循环周期p=M-1原根定义：a与M互素, 例S=32 M=231-1 a=16807或a=6303600165.1.4 伪随机数发生器的联合使用1 乘同余法与移位寄存器法联合使用首先用乘同余数法产生一个伪随机数，将其用二进制表示，然后进行移位操作，并进行浮点化，便可以得到一个（0，1）区间中的伪随机数。2 线性同余法和移位寄存器法联合使用如果用线性同余法和移位寄存器法分别产生两个（0，1）区间上的随机数序列、和、，用一个数组，如C(100)来存储100个伪随机数，i = 1，2，100。接着根据已产生的一个伪随机数，计算1+100*，取不超过1+100*的最大整数作为下标J，这样就选定了C（J），将C（J）中所存的随机数作为被选用的随机数。然后，再产生一个新的随机数，将它放入C（J）单元中去更新其中的内容。每次需要使用一个随机数时，都要执行上述的运算过程。3 等间隔地跳跃选用或几个伪随机数发生器轮换使用假若伪随机数发生器的周期很长，而需使用的随机数又不多时，可以每间隔一定的距离选用一个，其余的都丢掉。5.2 均匀分布伪随机数的检验1、随机性和均匀性检验1）频率检验对于（0，1）均匀分布数分成n组（0，），每组的理论频数为随机数个数，实际频数为Qi统计量服从分布，对于一定数量，若采用5%的置信度，查分布表，得，若，认为这批随机数在统计性能上是95%可信。2）粗略统计检验（参数检验） 为随机数，N为随机数个数如果明显不成立，就可否定随机性不够要求。2. 独立性检验1）相关系数检验n个独立的服从于0，1均匀分布的随机数U1，U2，Un均值协方差协方差估值：令 的均值，的方差：当n充分大，分布近似于正态分布N（0，1）2）联立表检验 把一单位正方形分成K2相等的小正方形把随机数数列Ui,(i=1,Ln)按受的次序组成（U1，Ue+1），L）设存入第(i,j)个小正方形的频数为,落入（i, j）的理论值为服从5.2.3 矩检验矩检验是检验随机数的观测值各阶矩与理论值的差别是否显著。在产生N个随机数，之后，可以给出观测值的各阶矩根据中心极限定理，统计量渐进服从N（0，1）分布。当给定置信度后，即可根据正态分布表确定临界值，如大于临界值，拒绝假设，否则接受假设。3 产生各种概率分布的随机数1.求逆法X为一个随机变量，它的分布函数为F（X），记为FX的逆函数，U为0，1均匀分布随机变量，则随机变量同X具有相同的分布函数F（X）算法：1）产生U 2）例：负指数分布随机变量产生负指数密度函数：其分布函数：设U为0，1均匀分布2舍选法设某一随机数变量的密度函数f(x)满足：当xb 或x1解：计算f(x)的最大值求解步骤：（1）根据r,s，求f(x)的最大值M （2）产生0，1均匀分布随机数R1，R2 （3）检验是否成立若成立R1为Beta分布的随机数，否则转（2）3 组合法在本节中我们要用到凸组合的概念，它的定义如下：设、是中点集X的k个点，若存在、 满足，使也属于X，则称为、（对于、 ）的凸组合。组合法的主要思想是这样的，当我们要生成的随机数数列服从的分布函数可以用其它分布函数，的凸组合表达，并且远比要简单时，我们可以先生成服从的随机数数列，然后再利用这些随机数数列得到服从的随机数数列。具体来说，我们假定对所有x，可以写成：这里，每一个是一个分布函数，同样若x为密度函数，则假定它可以写成这里是其它密度函数。在离散情况下，组合法依然适用。利用组合法产生随机数的步骤如下：1.产生一个正随机数J，使得 j = 1，2， 2.使，产生具有分布函数的随机数x，然后返回。我们很易了解由算法得到的x将有分布函数，因为我们有：有时我们能给出组合法的几何解释，例如对于X上一个具有密度的连续随机变量，我们可将下的面积分为、区域，对应于将分解为凸组合表示，然后我们可以认为第一步是选一个域，而第二步则是从所选域对应的分布中产生随机数。例 双指数（或拉普拉斯）分布具有密度函数，x为实数。由图2.5可见，除了因子0.5之外，可以看成是由两个背靠背的指数函数组成。我们可把表示为：这里表示集合A的指示函数，它定义为：于是，可看作和的凸组合，和都是密度函数，且。因此，我们可用和的组合来产生X。首先产生两个在0，1 上服从均匀分布的随机数R1，R2，如果，则令返回。同样，若，则令返回。4 经验分布法经验分布法又称为表搜索法，主要用于产生离散分布的随机数，也可通过离散近似抽样产生连续分布的随机数。现实中很多随机现象的理论分布往往是不知道的，而其经验分布常常是可以得到的，为了仿真这些随机现象，通常根据它们的经验分布来产生抽样值。下面介绍用经验分布法来产生离散分布随机数的方法。设随机变数X的取值的概率为，即 i = 1，2， ，k且 ，将0，1区间划分为k个小区间，每个区间长度分别等于、。令，i = 1，2， ，k。其中称为累积分布函数，即， 。现任取0，1上均匀分布的随机变数，若，则。这是因为我们有综上所述，产生离散分布的随机数主要步骤如下：（1） 编制如表5.3所示的表格，并存入计算机内。为了缩短搜索时间，累积分布函数可按排列计算；表5.3随机变数X的可能取值 累积分布函数 （2） 产生0，1上均匀分布的随机数r；（3） 进行表搜索，若，则。5 近似法近似法是指一种利用一些定理或公式来近似地产生所需随机数的方法，这种方法一般用于分布函数比较复杂，难以对其求解的情况，如正态分布。下面主要介绍用该方法产生正态分布随机数的问题。1利用中心极限定理设为n个的在0，1区间上的均匀分布随机数，它们相互独立，则有根据中心极限定理服从标准正态分布N（0，1）。如果作线性变换：则可以得到一个服从正态分布N（）的随机变量。在实际应用中，只要取就可以了。2Box-Maller近似方法设R1，R2为在0，1区间上服从均匀分布的随机数，利用Box-Maller公式可以产生两个服从标准正态分布N（0，1）的随机数。作业：1、请用线性同余法设计一个【0，1】均匀分布随机数产生算法，并给出1000个随