2.随机数

null随机数随机数OutlineOutline随机数的定义及产生方法 伪随机数 产生伪随机数的乘同余方法 产生伪随机数的乘加同余方法 Matlab中如何产生均匀分布的随机数 伪随机数序列的均匀性和独立性 随机数随机数随机模拟蒙特卡罗方法(Monte Carlo)是通过由具有已知分布的总体中抽取简单子样而展开的一类研究、计算方法， 如何从已知总体中抽取其简单子样在蒙特卡罗研究方法在中占有非常重要的地位。随机数随机数随机数是实现由已知分布抽样的基本量 在由已知分布的抽样过程中，将随机数作为已知量，用适当的数学方法可以由它产生具有任意已知分布的简单子样。 1.随机数的定义、性质及产生方法1.随机数的定义、性质及产生方法随机数的定义 随机数的性质 产生办法 随机数表 物理方法 随机数的定义 随机数的定义 在连续型随机变量的分布中，最简单而且最基本的分布是单位均匀分布。由该分布抽取的简单子样称为随机数序列，其中每一个体称为随机数。 单位均匀分布也称为［0，1］上的均匀分布， 其分布密度函数为： 分布函数为 ：随机数的性质 随机数的性质 由于随机数在蒙特卡罗方法中占有极其重要的位置，我们用专门的符号ξ表示。 由随机数序列的定义可知，ξ1，ξ2，…是相互独立且具有相同单位均匀分布的随机数序列。也就是说，独立性、均匀性是随机数必备的两个特点。 随机数具有非常重要的性质：对于任意自然数s，由s个随机数组成的s维空间上的点（ξn+1，ξn+2，…ξn+s）在s维空间的单位立方体Gs上均匀分布：随机数的产生方法--随机数表随机数的产生方法--随机数表随机数表 随机数表是由0，1，…，9十个数字组成，每个数字以0.1的等概率出现，数字之间相互独立。这些数字序列叫作随机数字序列. 如果要得到n位有效数字的随机数，只需将表中每n个相邻的随机数字合并在一起，且在最高位的前边加上小数点即可。例如，某随机数表的第一行数字为7634258910…，要想得到三位有效数字的随机数依次为0.763，0.425，0.891。 缺陷：因为随机数表需在计算机中占有很大内存，而且也难以满足蒙特卡罗方法对随机数需要量非常大的要求，因此，该方法不适于在计算机上使用。随机数的产生方法--物理方法随机数的产生方法--物理方法物理方法 利用某些物理现象，在计算机上增加随机数发生器。 利用放射性物质的放射性 利用计算机的固有噪声 一般情况下，任意一个随机数在计算机内总是用二进制的数表示的： 其中εi（i=1，2，…，m）或者为0，或为1。 随机数的产生方法--物理方法随机数的产生方法--物理方法利用物理方法在计算机上产生随机数，就是要产生只取0或1的随机数字序列，数字之间相互独立，每个数字取0或1的概率均为0.5。 缺陷： 用物理方法产生的随机数序列无法重复实现，不能进行程序复算，给验证结果带来很大困难。 需要增加随机数发生器和电路联系等附加设备，费用昂贵。该方法也不适合在计算机上使用。伪随机数伪随机数伪随机数 伪随机数存在的两个问 伪随机数的周期和最大容量伪随机数伪随机数在计算机上产生随机数最实用、最常见的方法是数学方法，即用如下递推公式： 产生随机数序列。对于给定的初始值ξ1,ξ2…，ξk，确定ξn+k，ｎ=1，2，…。经常使用的是k=1的情况，其递推公式为： 对于给定的初始值ξ1，确定ξn+1，ｎ=１,２… 伪随机数存在的两个问题伪随机数存在的两个问题用数学方法产生的随机数，存在两个问题： 递推公式和初始值ξ1,ξ2…，ξk确定后，整个随机数序列便被唯一确定。不满足随机数相互独立的要求。 由于随机数序列是由递推公式确定的，而在计算机上所能表示的[0，1]上的数又是有限的，因此，这种方法产生的随机数序列就不可能不出现无限重复。伪随机数存在的两个问题伪随机数存在的两个问题一旦出现这样的n’，n″ (n＇< n″ ), 使得下面等式成立： 随机数序列便出现了周期性的循环现象。对于k=1的情况，只要有一个随机数重复，其后面的随机数全部重复，这与随机数的要求是不相符的。 伪随机数存在的两个问题伪随机数存在的两个问题由于这两个问题的存在，常称用数学方法产生的随机数为伪随机数。 问题： 第一个问题：不能从本质上加以改变，但只要递推公式选得比较好，随机数间的相互独立性是可以近似满足的。 第二个问题：不是本质的。因为用蒙特卡罗方法解任何具体问题时，所使用的随机数的个数总是有限的，只要所用随机数的个数不超过伪随机数序列出现循环现象时的长度就可以了。伪随机数存在的两个问题伪随机数存在的两个问题优点： 用数学方法产生的伪随机数容易在计算机上得到； 可以进行复算，而且不受计算机型号的限制。生成伪随机数的基本要求生成伪随机数的基本要求产生的序列能够通过统计检验（独立性，均匀性检验）； 产生序列的计算方法简单易行，计算速度快，占用计算机内存少； 能够产生足够多的随机数；伪随机数的周期和最大容量 伪随机数的周期和最大容量 发生周期性循环现象的伪随机数的个数称为伪随机数的周期。对于前面介绍的情况，伪随机数的周期为n″－n＇。 从伪随机数序列的初始值开始，到出现循环现象为止，所产生的伪随机数的个数称为伪随机数的最大容量。前面的例子中，伪随机数的最大容量为n″ 。产生伪随机数的乘同余方法产生伪随机数的乘同余方法乘同余方法是由Lehmer在1951年提出来的； 对于任一初始值x1，伪随机数序列由下面递推公式确定： 其中a为常数。 乘同余方法在计算机上的使用乘同余方法在计算机上的使用为了便于在计算机上使用，通常取 ： Ｍ=2s 其中s为计算机中二进制数的最大可能有效位数 x1= 奇数 a = 52k+1 其中k为使52k+1在计算机上所能容纳的最大整数，即a为计算机上所能容纳的5的最大奇次幂。一般地，s=32时，a=513；s=48，a=515等。伪随机数序列的最大容量λ(M)=2s-2 。 乘同余方法是使用的最多、最广的方法，在计算机上被广泛地使用。产生伪随机数的乘加同余方法产生伪随机数的乘加同余方法产生伪随机数的乘加同余方法是由Rotenberg于1960年提出来的，由于这个方法有很多优点，已成为仅次于乘同余方法产生伪随机数的另一主要方法。 乘加同余方法的一般形式是，对任意初始值x1，伪随机数序列由下面递推公式确定： 其中a和c为常数。 M，x1，a，c的取值M，x1，a，c的取值为了便于在计算机上使用，通常取 M = 2s 其中s为计算机中二进制数的最大可能有效位数。 a = 2b + 1 (b≥2) c = 1 这样在计算中可以使用移位和指令加法，提高计算速度。 ExampleExample取 a = 13, c = 0, m = 31, x0 = 1, 产生的序列为： 1; 13; 14; 27; 10; 6; 16; 22; 7; 29; 5; 3; : : : 随机数相应为:0.0323; 0.4194; 0.4516; 0.8710; 0.3226; 0.1935; 0.5161; : : : 下一个是几？ Randexample.m计算机与随机数计算机与随机数生成随机数的方法 Matlab数值试验5.1:计算机与随机数5.1:计算机与随机数1960年，IBM a = 65539, c = 0, and m = 231. See the source file: randssp.m Matlab Ver.5 before a = 75 = 16807 c = 0 m = 231 - 1 = 2147483647 These values are recommended in a 1988 paper by Park and Miller. See the source file: randmcg.m 5.1:计算机与随机数5.1:计算机与随机数Matlab Ver.5, Ver. 6 In 1995, Version 5 of Matlab introduced a completely different kind of random number generator. The algorithm is based on work of George Marsaglia. His method does not use Lehmer's congruential algorithm. In fact, there are no multiplications or divisions at all. It is specically designed to produce floating-point values. See the source file: randtx.m5.2:Matlab数值试验5.2:Matlab数值试验Randgui (立方体内内切球计算pi） Rand help rand, doc rand hist State of rand rand(‘state’,0) 6.伪随机数序列的均匀性和独立性6.伪随机数序列的均匀性和独立性判断伪随机数序列是否满足均匀和相互独立的要求，要靠统计检验的方法实现。对于伪随机数的统计检验 一般包括两大类：均匀性检验和独立性检验。伪随机数的均匀性 伪随机数的均匀性 这里只考虑伪随机数序列ξ1,ξ2…，ξn全体作为子样时的均匀性问题。其中n为伪随机数序列的最大容量。 对于任意的0≤x≤1，令Nn(x)表示伪随机数序列ξ1,ξ2…，ξn中适合不等式 ξi< x i=1，2，…，n 的个数，则 标志伪随机数序列ξ1,ξ2…，ξn的均匀程度，称为均匀偏度。null将伪随机数序列ξ1,ξ2…，ξn从小至大重新排列 并令 ，则由δ(n)的定义， 容易证明 很明显，对于固定的ｎ，δ(n)的值越小越好。它是描述伪随机数序列均匀程度的基本量。伪随机数的独立性 伪随机数的独立性 对于任意 ，令 表示(ξ1,ξ2)， (ξ2,ξ3)，…， (ξn,ξn+1)中适合不等式 的个数，根据随机变量间相互独立的定义和频率近似概率 的方法，令 则ε(n)标志伪随机数序列ξ1,ξ2…，ξn的独立程度，简 称为独立偏度。对于固定的n,ε(n)的值越接近于零，伪 随机数序列的独立性越好。 null对于乘同余方法， 对于乘加同余方法， 因此，这两种方法的独立性都是很好的。 同伪随机数的均匀性问题一样，伪随机数序列的 独立性问题也是对它的全体讨论的。若只考虑伪 随机数的一部分，在通常情况下给出ε(i)是相当 因难的。因此，伪随机数序列的独立性问题的统 计检验方法同样是非常重要的。 作 业 作 业 用蒲丰投针法在计算机上计算π值，取a=4、l=3。 分别用理论计算和计算机模拟计算，求连续掷两颗骰子，点数之和大于6且第一次掷出的点数大于第二次掷出点数的概率。