第六章随机数生成器PPT讲稿.ppt

《第六章随机数生成器PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第六章随机数生成器PPT讲稿.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章随机数生成器第六章随机数生成器第1页，共25页，编辑于2022年，星期三随机数随机数l在离散系统仿真中，随机数是一个必不可少的基本元素l（0，1）均匀分布随机数是产生其他许多分布的随机数的基础l一个随机数序列必须满足两个重要的统计性质：均匀性和独立性第2页，共25页，编辑于2022年，星期三随机数的性质随机数的性质l均匀性 如果将区间0，1分为n个等长的子区间，那么在每个区间的期望观测次数为N/n，其中N为观测的总次数l独立性 观测值落在某个特定区间的概率与以前的观测值无关第3页，共25页，编辑于2022年，星期三随机数的产生方法随机数的产生方法l物理方法：利用某些物理过程来产生均匀分布

2、随机数l随机数表：利用物理过程得到的大量随机数，制成随机数表l随机数产生程序：按照一定的算法计算出具有类似于均匀分布随机变量的独立取样值性质的数伪随机数伪随机数第4页，共25页，编辑于2022年，星期三计算机产生随机数的要求计算机产生随机数的要求l产生的随机数要尽可能的逼近理想的均匀性和独立性统计性质l产生的随机数要有足够长的周期l产生随机数的速度要快，占用的内存空间要小l随机数必须是可重复的 对于给定的起始点或初始条件，应当能够产生相同的随机数序列，而且与正被仿真的系统完全无关第5页，共25页，编辑于2022年，星期三l产生随机数的算法是利用递推公式：第6页，共25页，编辑于2022年，星期

3、三平方取中法平方取中法l20世纪40年代由冯诺依曼提出的第一个随机数生成器l例：设有一个4位正整数Z0，对之取平方得到一个8位正整数（如果不够8位数，可以在左侧加上0补足8位）。而后取中间的4位获得一个新的4位正整数Z1。将Z1/10000得到一个0，1之间的小数，则获得第一个“随机数”U1。然后基于Z1重复上述操作，得到Z2和U2，依次类推第7页，共25页，编辑于2022年，星期三线性同余随机数生成器（线性同余随机数生成器（LCG）l其中，a称为乘法因子，c称为加法因子，m为模数l当a=1时，为加同余法；l当c=0时，为乘同余法；l当a1、c0时，为混合同余法第8页，共25页，编辑于2022

4、年，星期三例：例：l使用线性同余法产生随机数序列，其中Z0=27、a=17、c=43、m=100。解：Zk=(aZk-1+c)mod m Z1=(1727+43)mod 100=502mod100=2 Z2=(172+43)mod 100=77mod100=77 Z3=(1777+43)mod 100=1352mod100=52 U1=2/100=0.02,U2=77/100=0.77,U3=0.52第9页，共25页，编辑于2022年，星期三LCG的周期的周期l用LCG方法产生的随机数序列会出现周期循环的现象，一旦Zi取值和以前出现的某个值相同，此后的随机数序列就开始循环。循环的长度称为生成器

5、的周期；l由于0Zim-1，因此最大周期是m，称之为满周期；l为了产生成百上千的随机数，必须采用周期足够长的LCG，最好是满周期的生成器，这样对随机数的均匀性也很有利。第10页，共25页，编辑于2022年，星期三定理：定理：lLCG具有满周期，当且仅当以下3个条件成立：1.m和c互质；2.存在一个质数q，能够同时整除m和a-1；3.m和a-1能够被4整除。第11页，共25页，编辑于2022年，星期三模数模数m的取值的取值l为了使LCG的周期足够长，m的取值应该较大；l为了加快计算机的处理速度，选择m=2b，其中b为计算机CPU一次能处理的最大位数；目前b=32-1=31第12页，共25页，编辑

6、于2022年，星期三例：使用不同种子的周期例：使用不同种子的周期l使用乘同余法，对a=13、m=26=64且Z0=1,2,3,4,求产生器的周期。第13页，共25页，编辑于2022年，星期三iXiXiXiXi0123411326395224118593632142632041734514529582365750437371047833235945710927115331124919136155142511155151613第14页，共25页，编辑于2022年，星期三随机数的检验随机数的检验l为了检验产生的随机数序列是否满足均匀性和独立性，有必要进行一系列的检验：l均匀性检验（频率检验）l序列检

7、验l游程检验l相关性检验第15页，共25页，编辑于2022年，星期三均匀性检验均匀性检验其中，Oi为第i组中数据的观测值个数，Ei为第i组中数据的期望个数，n为组数。第16页，共25页，编辑于2022年，星期三均匀性检验均匀性检验 H0：Ri服从U0，1 H1：Ri不服从U0，1检验方法：选定一个显著性水平 如果 第17页，共25页，编辑于2022年，星期三序列检验序列检验l序列检验是运用 检验来检验随机数序列的n维均匀性，以此判断随机数序列的独立性。l假设Ui是独立同分布U(0,1)的随机变量，则构造n个d维随机变量：U1=(U1,U2,Ud),U2=(Ud+1,Ud+2,U2d),将0,1

8、等分为k个子区间，则在d维空间中共有kd个子区间，n个随机变量落在每个区间的个数期望值（期望频度）为n/kd。设fj1,j2,jd为落在子区间j1j2jd的观测值个数（观测频度），第18页，共25页，编辑于2022年，星期三序列检验序列检验 则第19页，共25页，编辑于2022年，星期三游程检验游程检验l游程检验是一种对独立性假设的更为直接的检验。l对Ui序列进行检验，以得到Ui的不间断子序列，每个子序列都是Ui单调增长单调增长的最长最长子序列，每个子序列称为游程。例：0.86,0.11,0.23,0.03,0.13,0.06,0.55,0.64,0.87,0.10第20页，共25页，编辑于2

9、022年，星期三游程检验游程检验给定一个有n个Ui的序列，对长度为1,2,3,4,5,6的游程进行计数，则可以定义则可构造如下检验统计量：第21页，共25页，编辑于2022年，星期三游程检验游程检验 如果n足够大(n4000)，R近似满足自由度为6的 分布。第22页，共25页，编辑于2022年，星期三相关性检验相关性检验0.12 0.01 0.23 0.28 0.89 0.31 0.64 0.28 0.83 0.93 0.99 0.15 0.33 0.35 0.91 0.41 0.60 0.27 0.75 0.88 0.680.49 0.05 0.43 0.95 0.58 0.19 0.360.69 0.87第23页，共25页，编辑于2022年，星期三相关性检验相关性检验设给定N个随机数x1,x2,xn,计算前后距离为j的样本相关系数：第24页，共25页，编辑于2022年，星期三相关性检验相关性检验第25页，共25页，编辑于2022年，星期三