伪随机数的生成.pptVIP

摘 要 在计算机上用数学的方法产生随机数列是目前通用的方法，它的特点是占用的内存少，速度快．用数学方法产生的随机数列是根据确定的算法推算出来的，严格说来并不是随机的，因此一般称用数学方法产生的随机数列为伪随机数列．不过只要用数学公式产生出来的伪随机数列通过统计检验符合一些统计要求，如均匀性、抽样的随机性等，也就是说只要具有真正随机数列的一些统计特征，就可以把伪随机数列当作真正的随机数列使用 . 由于是用算法产生的，因而本质上是决定性的，再加上计算机字长有限，所以无论用什么算法产生的数列，在统计特征上都不可能完全与从均匀分布中抽样所得的子样完全相同，因而只能要求尽可能地近似． 这种在计算机上用算法得到的统计性质上近似于[0，1]上均匀分布的数，一般就称为伪随机数，以区别于真正从[0，1]上均匀分布中抽样所得到的随机数．为了快速产生统计特征良好的伪随机数，数学上一般采用递推公式 Xn+1= f(Xn,Xn-1 ，? ，Xn-k)． 在给定一组初值X0，X-1,X-2, ? ，X-k 后，即可逐步求出X1，X2,X3? ．在此基础上产生随机数． 摘 要 随机数的产生 一．随机数的概念 对随机系统进行模拟，需要产生服从某种分布的一系列随机数. 定义：设随机变量X（总体）服从某种随机分布，对其进行了n次独立观察,得到一组简单随机样本 X1，X2，…，Xn ,满足： 1） X1，X2，…，Xn相互独立； 2）每一个X1，X2，…，Xn都与总体X 同分布. 利用某种方法得到一串数列r1 , r2 , … , rn 一、伪随机数生成算法 1.1取中法 1.2移位法 1.3同余法 1．1 取中法 产生伪随机数列最早的方法是平方取中法，即将一个2s位十进制随机数平方后得到的一个4 s位数，去头截尾取中间2s 位数作为一个新的随机数，重复上述过程便得到一伪随机数列．平方取中法的递推公式： Xn+1=-[X2n／10 s] (mod 102s )， (1) 产生伪随机数列: Rn=Xn/102s=Xn10-2s (2) 平方取中法的优点为在计算机上易于实现，内存占用少，但仍存在对小数目偏倚的现象，均匀性不好，数列的长度和周期难以确定，对初始数据的依赖很大． 1．1 取中法 对平方取中法进行改进，产生了乘积取中法，如果要产生具有10进制2s位的伪随机数列，任取两个初始随机数X0,X1，用递推公式: Xn+2=[Xn+1Xn／10s ] (mod 102s ) (3) 产生伪随机数列 Rn =Xn10-2s (4) 乘积取中法与平方取中法比较，从产生的伪随机数列长度及均匀性方面都有改善，但是数列长度还是不够，而且对初始值的依赖性很大． 1．2 移位法 电子计算机善于进行移位等逻辑运算，应用机器的这个特点有一类产生伪随机数列的方法，该方法称为移位法． 如果字长为32位的计算机，取一初始值X0，将X0左移7位得X01， 右移7位得,X02.将X01和 X02进行指令相加得到X1 ，再对X1 进行上述运算过程得到X2，这样多次重复可得正整数序列Xn，取 Rn=Xn2-32为[0，1]上均匀分布的伪随机数列通项． 1．2 移位法 这一算法 递推公式为:Xn+l= Xn 2 7 +Xn 2 -7 (mod2-32) ， 产生伪随机数列 Rn+1=Xn+1 2-32(5) 移位法运算速度快，但是对初始值的依赖性也很大，一般地初始值不能取得太小，选得不好会使伪随机数列长度较短 1．3 同余法 目前产生伪随机数列比较好的方法为同余法，其中有混合同余法、加同余法和乘同余 法 ．采用线性递推公式: Xn+1=λXn + C (mod M )，0≤ Xn+1 M ， 产生伪随机数列 :Rn=Xn ／M． (6) 其中 λ, c,M以及初值X0都是正整数．容易看出 满足0≤ Rn 1． 若c≠ 0且λ ≠ 1，则称这种方法为混合同余法．当c=0时，Xn+1= λ Xn (mod M )， 0≤ Xn+1 M ，Rn=Xn／M ， (7) 称为乘同余法． 1．3 同余法 当λ=1 ，C≠ 0时，Xn+1=Xn+C (mod M)，0≤ Xn+1 M ， Rn=Xn ／M， (8) 称为加同余法． 虽然加同余法产生的序列周期长，电子计算机实现也很方便，只要进行加法及移位运算即可完成，但从理论上看，所得到随机数列的性质一般不如乘同余法和混合同余法． 若 λ =c=1，则有Xn+1=Xn+1(mod M)．这样构成的序列虽然周期可以达到M，但不是随机的。因此乘子λ ，增量C的选取是非常重要的. 二、Monte-Carlo方法设计