第3章 随机数的生成2

1、第第3 3章章 随机数的生成及检验随机数的生成及检验本章主要介绍三部分的内容：本章主要介绍三部分的内容：3.1 3.1 随机数的生成及本质随机数的生成及本质3.2 3.2 常用的随机数发生器常用的随机数发生器3.3 3.3 均匀性检验均匀性检验3.4 3.4 独立性检验独立性检验3.1 随机数的生成及本质 关于随机数生成方法的研究已有很长的历史。最早的随机数关于随机数生成方法的研究已有很长的历史。最早的随机数是用手工实现的，如抽签、发纸牌、从罐子中摸取带数字的球等是用手工实现的，如抽签、发纸牌、从罐子中摸取带数字的球等方法。其中，有些方法至今仍然还采用。方法。其中，有些方法至今仍然还采用。 随

2、着随着Monte-CarloMonte-Carlo方法的出现，方法的出现，2020世纪初出现了生成随机数的世纪初出现了生成随机数的机械装置和电子装置。但是机械装置和电子装置不能重复生成与机械装置和电子装置。但是机械装置和电子装置不能重复生成与原来完全相同的随机数，对计算结果无法进行检查，并且生成过原来完全相同的随机数，对计算结果无法进行检查，并且生成过程比较复杂。因此，它们未能得到进一步推广。程比较复杂。因此，它们未能得到进一步推广。 目前，在用计算机生成随机数的方法中，一类使用最广、发目前，在用计算机生成随机数的方法中，一类使用最广、发展较快的方法是数学方法，其特点是占用内存少、速度快并且便

3、展较快的方法是数学方法，其特点是占用内存少、速度快并且便于检查。于检查。3.1 随机数的生成及本质 用数学方法生成随机数是指按照一定的算法（递推公式），来用数学方法生成随机数是指按照一定的算法（递推公式），来生成生成“随机随机”数列（也称随机数流）。我们只要任意给定一个初始数列（也称随机数流）。我们只要任意给定一个初始值（也称种子值），当调用该算法时，就可以按确定的关系计算出值（也称种子值），当调用该算法时，就可以按确定的关系计算出下一个下一个“随机随机”数，然后，以新生成的随机数作为第二个种子值，数，然后，以新生成的随机数作为第二个种子值，再计算出新的随机数。多次调用该算法就可以生成一个再计

4、算出新的随机数。多次调用该算法就可以生成一个“随机数随机数”序列。序列。 这种用算法生成的这种用算法生成的随机数，只要给定初始的种子值，则以后所随机数，只要给定初始的种子值，则以后所生成的生成的“随机随机”数都是确定的数值，从本质上说这并不具有真正的数都是确定的数值，从本质上说这并不具有真正的随机性，因此称这种方法为伪随机数随机性，因此称这种方法为伪随机数PRN（Pseudo Random Number）。用数学方法生成用数学方法生成随机数所依赖的算法和程序就称为随机随机数所依赖的算法和程序就称为随机数发生器。数发生器。3.1 随机数的生成及本质 如果精心设计算法，就可以生成具有真正随机数的统

5、计性质如果精心设计算法，就可以生成具有真正随机数的统计性质的伪随机数。通常，只要所生成的伪随机数能通过一系列统计检的伪随机数。通常，只要所生成的伪随机数能通过一系列统计检验（如独立性、均匀性）就可以把它们作为真正的随机数使用。验（如独立性、均匀性）就可以把它们作为真正的随机数使用。 一个优良的一个优良的随机数发生器应当具有以下特性：随机数发生器应当具有以下特性： （1）生成的随机数要具有总体样本的统计性质，如分布的均）生成的随机数要具有总体样本的统计性质，如分布的均匀性、抽样的随机性、数列间的独立性等。匀性、抽样的随机性、数列间的独立性等。 （2）生成的随机数流要有足够长的周期，以满足仿真计算

6、的）生成的随机数流要有足够长的周期，以满足仿真计算的需要。需要。 （3）生成随机数流的速度要快，占用计算机的内存要少，具）生成随机数流的速度要快，占用计算机的内存要少，具有完全可重复性。有完全可重复性。 3.2 常用的随机数发生器 生成随机数的方法经历了一段漫长的发展过程，下面介绍几种生成随机数的方法经历了一段漫长的发展过程，下面介绍几种有代表性的算法，主要有：有代表性的算法，主要有： 早期的随机数发生器：早期的随机数发生器：平方取中随机数发生器、乘积取中随平方取中随机数发生器、乘积取中随机数发生器、常数乘子法、斐波那契法（机数发生器、常数乘子法、斐波那契法（Fibonacci）等；等； 线性

7、同余随机数发生器（混合同余线性同余随机数发生器（混合同余随机数随机数发生器、发生器、乘同余随乘同余随机数发生器）；机数发生器）；3.2.1 早期的随机数发生器1. 平方取中随机数发生器平方取中随机数发生器的位数的一半为正整数初始值为002221),(10/10mod10 xkxxuxxknnkknn 平方取中随机数发生器是由冯平方取中随机数发生器是由冯.纽曼于纽曼于1940年提出的，其递推年提出的，其递推公式为：公式为：3.2.1 早期的随机数发生器其中，其中， 表示取表示取 的整数部分，例如：的整数部分，例如：knx1021knx102158.5)1(的位数的一半为正整数初始值为002221

8、),(10/10mod10 xkxxuxxknnkknn51.5)2( 55)3(3.2.1 早期的随机数发生器kknx22110mod10对对进行模为进行模为 的求余运算。我们看下面的例子：的求余运算。我们看下面的例子：knx1021k210的含义为：的含义为：上式中上式中的位数的一半为正整数初始值为002221),(10/10mod10 xkxxuxxknnkknn3.2.1 早期的随机数发生器例如：例如：表示对整数表示对整数N 进行模为进行模为 M 的求余运算，其含义为：的求余运算，其含义为：MN modMMNNMNmod3424567456645456mod45)1(045459545

9、9945459mod45)2(3.2.1 早期的随机数发生器初始初始值值x0为为 2k 位非负整数，关于位非负整数，关于k的取值的取值一般最小取一般最小取2，为方便有时也，为方便有时也取取1。的位数的一半为正整数初始值为002221),(10/10mod10 xkxxuxxknnkknnnu的计算表达式为：的计算表达式为：knx210/ 为为0，1区间上的数。区间上的数。nu3.2.1 早期的随机数发生器例例3.1 取取k=1， x0 =76，求由求由“平方取中法平方取中法”可以得到如下随机数。可以得到如下随机数。577676220 x77100mod577100mod10577610mod1

10、07610mod10222201xx取取解：解：3.2.1 早期的随机数发生器77. 0100/10/1211xxu则则592977221x92. 0100/22xu取取则则由于由于922x依次取下去，我们可以得到如下表：依次取下去，我们可以得到如下表：3.2.1 早期的随机数发生器n1234101112131457765929846421160841705600250004000077924611845200000.770.920.460.110.840.050.02000021nxnxnu由上例可以看出，由于由上例可以看出，由于 k 取值较小，很快进入退化状态；当取值较小，很快进入退化状态

11、；当 k 取值取值较大时，将使退化现象延迟。较大时，将使退化现象延迟。3.2.1 早期的随机数发生器2. 乘积取中法随机数发生器乘积取中法随机数发生器位正整数为、及初始值为kxxxxxuxxxknnkknnn2,10/10mod10101021211 乘积取中法随机数发生器的其递推公式为：乘积取中法随机数发生器的其递推公式为：乘积取中法随机数发生器中要有乘积取中法随机数发生器中要有两两个种子值为个种子值为x0、x1， x0、x1为为 位非负整数，位非负整数，k一般最小取一般最小取2；k23.2.1 早期的随机数发生器例例3.2 取取k=2， x0 =5167， x1 =3729，求由求由“乘积

12、取中法乘积取中法”可以得到可以得到不同的随机数。不同的随机数。192677433729516710 xx26772x2677.010000/21 xu解：由于解：由于取取则则0998253399825332677372921 xx9825. 010000/32 xu取取则则同理同理98253x依次取下去，我们可以得到如下表：依次取下去，我们可以得到如下表：（注意）注意）3.2.1 早期的随机数发生器n1234561926774309982533263015252962237518762345474379292677982530156223762343790. 26770. 98250. 301

13、50. 62230. 76230. 4379nnxx11nxnu “乘积取中法乘积取中法”的周期比的周期比“平方取中法平方取中法”长，均匀性也有所改长，均匀性也有所改善，但主要缺点是最后仍要进入退化状态。善，但主要缺点是最后仍要进入退化状态。3.2.1 早期的随机数发生器3.常数乘子发生器常数乘子发生器MxxuxMxknnkknn及乘子初始值为022110/10mod10 常数乘子发生器是乘积取中法随机数发生器的一种变形，这常数乘子发生器是乘积取中法随机数发生器的一种变形，这种方法需要选取一个种方法需要选取一个 2k 位的非负整数位的非负整数M为常数因子，其递推公为常数因子，其递推公式为：式为

14、：常数乘子发生器中的常数乘子发生器中的x0为为2k位非负整数，位非负整数，k一般最少取一般最少取2。3.2.1 早期的随机数发生器例例3.3 取取k=2， M=3987， x0=7223，求由求由常数乘子法可以得到不同的常数乘子法可以得到不同的随机数。随机数。解解798110mod28798110mod01.28798110mod102879810110mod10222222222201xMx7981.010000/798110/2211xu3.2.1 早期的随机数发生器同理同理820210mod31820210mod47.31820210mod103182024710mod102222222

15、22212xMx8202.010000/820210/2222xu3.2.1 早期的随机数发生器n1234562879810131820247327013742796083138307096122400907981820270139608307324000. 79810. 82020. 70130. 96080. 30730. 24001nMxnxnu 同乘积取中法一样，常数乘子法的周期比平方取中法长，均匀同乘积取中法一样，常数乘子法的周期比平方取中法长，均匀性也有所改善，但主要缺点是最后仍要进入退化状态。性也有所改善，但主要缺点是最后仍要进入退化状态。依次取下去，我们可以得到如下表：依次取下

16、去，我们可以得到如下表：3.2.1 早期的随机数发生器4. 斐波那契发生器斐波那契发生器10111/mod)(xxmxumxxxnnnnn及初始值为 斐波那契（斐波那契（Fibonacci）法基于法基于Fibonacci 序列，其递推公式序列，其递推公式为：为：其中，其中， x0、x1、m为为非负整数非负整数。3.2.1 早期的随机数发生器例例3.4 取取x0 =0， x1 =1，m=8 ，求由上述递推公式求由上述递推公式可以得到不同的随可以得到不同的随机数。机数。则则18mod1mod)(102mxxx125.08/1/21mxu解：解：3.2.1 早期的随机数发生器同理同理则则28mod2

17、mod)(213mxxx25.08/2/32mxu3.2.1 早期的随机数发生器 若继续计算可得，若继续计算可得， u1 =u13=0.125，且从且从n=13开始，开始，un循环取循环取u1从从到到u13的值，周期的值，周期T=12m。此法的优点是计算方便，周期长，缺点是此法的优点是计算方便，周期长，缺点是序列中的数重复出现。序列中的数重复出现。n1234567891011121312350552710110.1250.250.3750.62500.6250.6250.250.8750.12500.1250.1251nxnu依次取下去，我们可以得到如下表：依次取下去，我们可以得到如下表：3.

18、2.2 线性同余随机数发生器 目前在离散系统仿真中应用最广泛的随机数发生器之一是线性目前在离散系统仿真中应用最广泛的随机数发生器之一是线性同余随机数发生器，简称同余随机数发生器，简称LCG ( Linear Congruence Generator)LCG ( Linear Congruence Generator)。此方法是由此方法是由LehmerLehmer于于19511951年提出的，其递推公式为：年提出的，其递推公式为： 其中，其中， m为模数，为模数，a为乘子（常数），为乘子（常数），c为增量（常数）；为增量（常数）；m，a，c，以及初始值以及初始值x0均为非负整数。均为非负整数。0

19、1/mod)(xmxumcxaxnnnn初始值为3.2.2 线性同余随机数发生器 由上述递推公式得到的由上述递推公式得到的xn满足：满足： ，从而，从而 至多能至多能取取m个不同的整数。个不同的整数。mxn0nx 称称数列数列 x xn n 重复值之间的最短长度为重复值之间的最短长度为 x xn n 的周期，记为的周期，记为T T。若若T T= =m m，则称为满周期的。下面举例说明线性同余随机数发生器的应用。则称为满周期的。下面举例说明线性同余随机数发生器的应用。例例3.5 取取a =3，c =1，m=8 ，x0 =1，利用利用线性同余法产生线性同余法产生随机数。随机数。解：解：48mod4

20、8mod)13(01xx5.08/48/11 xu3.2.2 线性同余随机数发生器同理同理58mod138mod)13(12xx625.08/58/22 xu08mod168mod)13(23xx08/08/33 xu3.2.2 线性同余随机数发生器n1234567891041316141316141345014501450.50.62500.1250.50.62500.1250.50.625nunx131nx依次取下去，我们可以得到如下表：依次取下去，我们可以得到如下表：3.2.2 线性同余随机数发生器n1234567891041316141316141345014501450.50.625

21、00.1250.50.62500.1250.50.625nunx131nx从从n=5开始，开始， ， ， un循环取循环取u1从到从到 u4 的值，周期的值，周期T=48=m，不是满周期的。不是满周期的。5.015 uu625.026 uu3.2.2 线性同余随机数发生器 例例3.6 取取a =5，c =5，m=8 ，x0 =5， ，则由则由线性同余法线性同余法可以得到可以得到不同的随机数，如下表：不同的随机数，如下表：n123456789103035202505405303563412705630.750.3750.50.1250.250.87500.6250.750.375nunx551n

22、x 从从n=9开始，开始， ， ，un 循环取循环取 u1 从到从到 u8 的的值，值， 周期周期 T=8，即周期等于即周期等于 m，此时是满周期情形。此时是满周期情形。 从上述两个例子可以看出，从上述两个例子可以看出， 参数参数 m，a，c，以及初值以及初值x0 的选取的选取十分关键，若参数十分关键，若参数 m，a，c，以及初值以及初值 x0 选得合适，周期选得合适，周期T可以达可以达到最大值到最大值 m，即是满周期的。即是满周期的。75. 019uu375. 0210uu3.2.2 线性同余随机数发生器 根据根据 c c 的取值，将线性同余随机数发生器分为两类：若的取值，将线性同余随机数发

23、生器分为两类：若c 0的的线线性同余随机数发生器性同余随机数发生器称为称为混合同余发生器混合同余发生器；若；若 c=0的的线性同余随机数线性同余随机数发生器发生器称为称为乘同余发生器乘同余发生器，即，即“乘同余发生器乘同余发生器”是是“混合同余发生器混合同余发生器”的特例。的特例。 下面的定理给出了下面的定理给出了混合同余发生器可达到满周期的条件。混合同余发生器可达到满周期的条件。 定理定理4.1 若满足下列三个条件，则混合同余发生器可达到满周期：若满足下列三个条件，则混合同余发生器可达到满周期： （1）c与与m互素（互素（可同时整除可同时整除c与与m的整数只有的整数只有1）；）； （2）对任

24、意素数）对任意素数q ，若若q 能能整除整除m，则则q 也能整除也能整除 a-1； （3）若若4能整除能整除 m，则则4也能整除也能整除 a-1。3.3 均匀性检验 均匀性检验是检验某个发生器生成的随机数是否均匀地分布均匀性检验是检验某个发生器生成的随机数是否均匀地分布在在0，1区间上。实际上，该方法是检验经验频率与理论频率的差区间上。实际上，该方法是检验经验频率与理论频率的差异是否显著。因此，也称为频率检验。均匀性检验主要有两种方异是否显著。因此，也称为频率检验。均匀性检验主要有两种方法：法： 检验和柯尔莫哥洛夫检验和柯尔莫哥洛夫斯米尔诺夫检验（斯米尔诺夫检验（K S）检检验，这里我们重点介

25、绍验，这里我们重点介绍 检验。检验。21. 检验检验2 设设 是一组待检验的随机数，并假设它们是一组待检验的随机数，并假设它们独立同服从独立同服从U0，1分布。分布。 检验首先建立统计假设：检验首先建立统计假设：nuuu,.,212 建立统计假设：建立统计假设： H0 : 随机数随机数ui均匀地分布在区间均匀地分布在区间0 , 1上。上。2称称 为理论为理论频数，即从理论上说应该有个随机数频数，即从理论上说应该有个随机数落入第落入第 i 个小区个小区间。间。3.3 均匀性检验 检验的具体步骤为：检验的具体步骤为：2（1）将）将0，1区间分成区间分成m个不相交的小区间：个不相交的小区间：(2)由

26、均匀性假设，由均匀性假设， 落入第落入第 i 个小区间的概个小区间的概率为率为1/m，则落入第则落入第i个区间的随机数可由计算下式：个区间的随机数可由计算下式：),.,2,1(),1mimimi),.,2,1(njuj),.,2,1(1mimnmnpiip3.3 均匀性检验miimiiiimnnnmppn12122)()(（4）构造下列统计量构造下列统计量(3) 计算随机数落入区间计算随机数落入区间 的个数的个数称称 为经验为经验频数，即频数，即落入第落入第 i 个小区间的实际个小区间的实际随机数的个数随机数的个数。,1mimi ),.,2,1(mini则构造的统计量则构造的统计量 渐进服从渐

27、进服从 分布。分布。)1(2m2in3.3 均匀性检验（6）根据所给的数据，计算出根据所给的数据，计算出 的值，代入下式的值，代入下式(5)对于给定水平对于给定水平 ，查，查 分布表得临界值分布表得临界值 ，使得，使得2)1(2m)1(22mP2)1(22m则可认为经验频数与理论频数没有显著差异，即则可认为经验频数与理论频数没有显著差异，即随机数随机数ui均匀地均匀地分布在区间分布在区间0 , 1上上；否则认为经验频数与理论频数有显著差异差；否则认为经验频数与理论频数有显著差异差异显著，从而认为假设不成立。异显著，从而认为假设不成立。计算出计算出 的值，若的值，若miimiiiimnnnmpp

28、n12122)()(in3.3 均匀性检验x0)1(2m2对于给定水平对于给定水平 ， 分布表得临界值分布表得临界值 的含义为：的含义为：2)1(2m注意：这里的注意：这里的 为单边临界值。而标准正态分布、为单边临界值。而标准正态分布、t 分分布一般是双边临界值。布一般是双边临界值。)1(2m3.3 均匀性检验样 本 量 n 分 组 区 间 数 m 100 n1/2到 n/5 检验的区间分组：检验的区间分组：23.3 均匀性检验例例3.7 7 某某随机数发生器生成随机数发生器生成100个随机数，试检验随机数的均匀性，个随机数，试检验随机数的均匀性，其中其中 。0.340.900.250.890

29、.870.440.120.210.460.670.830.760.790.640.700.810.940.740.220.740.960.990.770.670.560.410.520.730.990.020.470.300.170.820.560.050.450.310.780.050.790.710.230.190.820.930.650.370.390.420.990.170.990.460.050.660.100.420.180.490.370.510.540.010.810.280.690.340.750.490.720.430.560.970.300.940.960.580.730

30、.050.060.390.840. 240. 400.640.400.190.790.620.180.260.970.880.640.470.600.110.290.7805.03.3 均匀性检验解：将解：将0，1区间等分成区间等分成10个子区间（即个子区间（即m=10），），并统计出并统计出随机数随机数序列落在各子区间的个数（经验频数序列落在各子区间的个数（经验频数 ）分别为：）分别为： 7，9，8，9，14，7，10，15，9，12即落入区间即落入区间0，0.1）的数据为）的数据为7个；落入区间个；落入区间0.1，0.2）的数据为）的数据为9个；落入区间个；落入区间0.2，0.3）的数据为

31、）的数据为8个；落入区间个；落入区间0.3，0.4）的）的数据为数据为14个；落入区间个；落入区间0.4，0.5）的数据为）的数据为7个；落入区间个；落入区间0.5，0.6）的数据为）的数据为10个等。显然理论频数为个等。显然理论频数为10，则由下式：，则由下式：in7)10(1.0)(1012122iimiiiinppn对于对于 ，查，查 分布表确定单边临界值分布表确定单边临界值05.02)9(295.0其中，其中， 对应的自由度为对应的自由度为9。)9(295.03.3 均匀性检验自由度0.250.5000.7500.9000.9500.9750.99010.1020.4551.3232.

32、7063.8415.0246.63521.5751.3862.7734.6055.9917.3789.21031.2132.3664.1086,2517.8159.34811.345495.8998.34311.38914.68416.91919.02321.6661 由于由于919.16)9(7295.02 故可接受这故可接受这100个个随机数构成的随机数序列均匀地分布在随机数构成的随机数序列均匀地分布在0，1区区间上的假设。间上的假设。查表得查表得919.16)9(295.0对应于不同自由度的对应于不同自由度的 分布的临界表为：分布的临界表为：23.3 均匀性检验2. 柯尔莫哥洛夫柯尔莫哥

33、洛夫斯米尔诺夫检验斯米尔诺夫检验 柯尔莫哥洛夫柯尔莫哥洛夫斯米尔诺夫检验（斯米尔诺夫检验（Kolmogorov-Smirnov）是连续分布的拟合性检验，简称是连续分布的拟合性检验，简称K-S检验。它检验检验。它检验的是样本的经验分布函数与总体的分布函数间的差异是否显著。的是样本的经验分布函数与总体的分布函数间的差异是否显著。 K-S检验的具体做法是：检验的具体做法是：其经验分布函数为其经验分布函数为（1）将）将随机数随机数 从小到大排序，排列后记为从小到大排序，排列后记为nuuu,.,21)()2()1(,.,nuuu)()1()()1(1)1,.,2,1(0)(niininuxniuxuux

34、xF3.3 均匀性检验2. 柯尔莫哥洛夫柯尔莫哥洛夫斯米尔诺夫检验斯米尔诺夫检验 (2) 将将 与与U0，1的分布函数的分布函数 比比较较: 其中，其中， 表达式如下：表达式如下：计算最大偏差：计算最大偏差：,maxnnnDDD)( xFn)10()(xxxF111000)(xxxxxFnnDD、理论分布为：理论分布为：3.3 均匀性检验2. 柯尔莫哥洛夫柯尔莫哥洛夫斯米尔诺夫检验斯米尔诺夫检验 (3) 注意注意 渐进服从柯尔莫哥洛夫渐进服从柯尔莫哥洛夫斯米尔诺夫分布。对于水平斯米尔诺夫分布。对于水平 查查K-S分布表得临界值分布表得临界值 ，使得，使得（4）若）若 则可接受假设，即认为经验分

35、布函数与则可接受假设，即认为经验分布函数与0，1区间上的均匀分布函数之间没有显著差异；否则，认为经验区间上的均匀分布函数之间没有显著差异；否则，认为经验分布函数与分布函数与0，1区间上的均匀分布函数之间有显著差异。区间上的均匀分布函数之间有显著差异。nD)(nD)(nDDPn)(nDDnmax)()(max)(1)()(1iniiinninuniuFuFD1max)()(max)(1)1()(1niuuFuFDiniininin3.3 均匀性检验 例例4.9 9 给定水平给定水平 ，对于下列，对于下列10个随机数用个随机数用K-S法检验法检验其均匀性。其均匀性。0.340.900.250.89

36、0.870.440.120.210.460.6705.0把随机数由小到大排列，并将相关数据列表如下：把随机数由小到大排列，并将相关数据列表如下：i123456789100.120.210.250.340.440.460.670.870.890.90.10.20.30.40.50.60.70.80.91-0.02-0.010.050.060.060.140.03-0.070.010.10.120.110.050.040.04-0.040.070.170.090)(iu)(/iunini /niui/)1()(第四行第四行 、第五行的元素可以通过下列方法得到：、第五行的元素可以通过下列方法得到：3

37、.3 均匀性检验i123456789100.120.210.250.340.440.460.670.870.890.90.10.20.30.40.50.60.70.80.91-0.02-0.010.050.060.060.140.03-0.070.010.1)(iu)(/iunini /第四行第四行 = 第三行第三行 - 第二行第二行第五行第五行 = 由第二行按箭头方向减去第三行由第二行按箭头方向减去第三行i123456789100.120.210.250.340.440.460.670.870.890.90.10.20.30.40.50.60.70.80.910.120.110.050.04

38、0.04-0.040.070.170.090)(iuni /niui/)1()(3.3 均匀性检验最后得到相关数据列表：最后得到相关数据列表：i123456789100.120.210.250.340.440.460.670.870.890.90.10.20.30.40.50.60.70.80.91-0.02-0.010.050.060.060.140.03-0.070.010.10.120.110.050.040.04-0.040.070.170.090)(iu)(/iunini /niui/)1()( 由上表可得由上表可得 ，14.010D 故故17.017.0,14.0max10D)10

39、(05.0D查查K-S分布表得临界值：分布表得临界值： ，对应的自由度为，对应的自由度为10。17.010D3.3 均匀性检验自由度自由度10.9500.9750.99520.7760.8420.92930.6420.7080.82840.5640.6240.73350.5100.5650.66960.4700.5210.61870.4380.4860.57780.4110.4570.54390.3880.4320.514100.3680.4100.49010.0D05.0D01.0D对应于不同自由度及置信水平的对应于不同自由度及置信水平的K-S分布的临界值为：分布的临界值为：3.3 均匀性检

40、验查查K-S分布表得临界值为：分布表得临界值为：41.0)10(17.005.010DD因此，可以接受总体分布与均匀分布函数之间没有显著差异的假设。因此，可以接受总体分布与均匀分布函数之间没有显著差异的假设。41.0)10(05.0D由于由于要求在显著水平要求在显著水平 下，用下，用K-S法检验其均匀性。法检验其均匀性。3.3 均匀性检验 例例4.10 已知已知5个观察数据分别为个观察数据分别为0.440.810.140.050.9305.0i123450.050.140.440.810.930.200.400.600.801.000.150.260.16-0.010.070.05-0.060

41、.040.210.13)(iu)(/iunini /niui/)1()(把随机数由小到大排列，分别求把随机数由小到大排列，分别求555DDD、将相关数据列表如下将相关数据列表如下：3.3 均匀性检验 由上表可得由上表可得 ，26.05D查查K-S分布表得临界值为分布表得临界值为：21.05D 故故26.021.0,26.0max5D26.0565.0)5(505.0DD因此，通过均匀性检验。因此，通过均匀性检验。自由度自由度10.9500.9750.99530.6420.7080.82840.5640.6240.73350.5100.5650.66910.0D05.0D01.0D对应于不同自由

42、度及置信水平的临界值为：对应于不同自由度及置信水平的临界值为：565.0)5(05.0D由于由于3.3 均匀性检验 检验和检验和K-S检验都能较好地用于检验随机数发生器的均匀性，检验都能较好地用于检验随机数发生器的均匀性，但但K-S检验可用于小样本检验，检验可用于小样本检验， 检验需要的样本量较大。检验需要的样本量较大。223.4 独立性检验 独立性检验是独立性检验是检验随机数序列检验随机数序列 的统计相关性是的统计相关性是否显著。通常检查随机数序列的连续上升或下降的情形。常用的方否显著。通常检查随机数序列的连续上升或下降的情形。常用的方法有：相关系数检验和连贯性检验。法有：相关系数检验和连贯

43、性检验。1. 相关系数检验相关系数检验 设设 是一组待检验的随机数，假设是一组待检验的随机数，假设k 阶自相关系数阶自相关系数),.,2,1(0mkknuuu,.,21 相关系数检验反映了随机变量之间的线性相关程度。若两个随相关系数检验反映了随机变量之间的线性相关程度。若两个随机变量独立，它们的相关系数必为零，故可以利用相关系数来检验机变量独立，它们的相关系数必为零，故可以利用相关系数来检验随机数的独立性。随机数的独立性。nuuu,.,21 考虑样本的考虑样本的 k 阶自相关系数阶自相关系数3.4 独立性检验当当 充分大，且充分大，且 成立时，下式渐近服从成立时，下式渐近服从 分布：分布：在实

44、际检验中，在实际检验中，m的取值在的取值在10到到20之间。之间。niiknikiikuunuuuukn121)(11)(1kn 0k)1 ,0(N),.,2,1(mkknvkk3.4 独立性检验 利用统计量利用统计量 进行相关性检验，即对于显著性水平进行相关性检验，即对于显著性水平 ， 当当 时，接受相关系数时，接受相关系数 的假设；否则，拒绝的假设；否则，拒绝假设。假设。0kkv2/1 Zvk3.4 独立性检验2. 扑克检验扑克检验 扑克检验主要根据扑克检验主要根据一个随机数中数字重复出现的频率，一个随机数中数字重复出现的频率，检验随机检验随机数组合的规律性。数组合的规律性。 设设随机数用

45、三位数表示为：随机数用三位数表示为：ui=0. a1 a2 a3， 设设A1 : a1、 a2、 a3中三位中三位数字都不相同；数字都不相同； A2 : a1、 a2、 a3中有且仅有中有且仅有2位数字相同；位数字相同； A3 : a1、 a2、 a3中三位数字都相同。中三位数字都相同。假如假如ai独立，且同服从独立，且同服从U0 , 1分布，则有分布，则有01.010/10)(27.010/910)(72.010/8910)(33332322311APpCAPpAPp3.4 独立性检验2. 扑克检验扑克检验 由此可计算三个事件发生的理论频数为：由此可计算三个事件发生的理论频数为： 设实际发生

46、频设实际发生频数数为为mk，则下列统计量渐近服从则下列统计量渐近服从 分布分布)3,2, 1(knpqkk)2(23122)(kkkkqqm 故可利用故可利用 2分布进行假设检验，可以检验随机数列的组合规律性，分布进行假设检验，可以检验随机数列的组合规律性，从而判断其独立性。从而判断其独立性。3.4 独立性检验2. 扑克检验扑克检验 例例4.11 若有若有1000个用三位小数表示的个用三位小数表示的随机数，经统计知三位数字随机数，经统计知三位数字都不相同有都不相同有680个数，恰有两位数字相同有个数，恰有两位数字相同有289个，三位数字都相同有个，三位数字都相同有31个。在显著水平个。在显著水

47、平 下，试检验这组数据是否独立。下，试检验这组数据是否独立。 解：由已知解：由已知05.0720100072.0100011pq270100027.0100022pq3.4 独立性检验由下式计算得由下式计算得又又65.47)(3122kkkkqqm下面查表求下面查表求10100001.0100033pq6801m2892m313m)2(205.03.4 独立性检验自由度0.250.5000.7500.9000.9500.9750.99010.1020.4551.3232.7063.8415.0246.63521.5751.3862.7734.6055.9917.3789.21031.2132.

48、3664.1086,2517.8159.34811.345495.8998.34311.38914.68416.91919.02321.6661对应于不同自由度的对应于不同自由度的 分布的临界表为：分布的临界表为：2991.5)2(205.0 对于对于 ，查表得：，查表得：05.03.4 独立性检验 由于由于991.5)2(65.47205.02故这些数据不独立。故这些数据不独立。 所谓所谓 连贯性连贯性检验是检验一组随机数中每隔一些数字是否出现连续检验是检验一组随机数中每隔一些数字是否出现连续增大或连续减少的现象，从而检验这组数据是否相互独立。增大或连续减少的现象，从而检验这组数据是否相互独

49、立。可分为趋可分为趋势连检验和正负连检验。势连检验和正负连检验。 下表中一组数据，无论是采用下表中一组数据，无论是采用K-S检验还是采用检验还是采用 检验，检验结检验，检验结果都是均匀分布的，不难发现，这组数据是每隔果都是均匀分布的，不难发现，这组数据是每隔10个数就产生连续增个数就产生连续增大。我们的问题是：虽然这组数据是均匀的，它们是否是独立的？因大。我们的问题是：虽然这组数据是均匀的，它们是否是独立的？因此，需要采用连贯性此，需要采用连贯性检验来检查这组数据是否独立。检验来检查这组数据是否独立。20.080.090.230.290.420.550.580.720.890.910.110.

50、160.180.310.410.530.710.730.740.840.020.090.300.320.450.470.690.740.910.950.120.130.290.360.380.540.680.860.880.913.4 独立性检验 独立性检验的比较重要的方法是采用独立性检验的比较重要的方法是采用 连贯性连贯性检验进行的。检验进行的。 （1.）趋势连检验）趋势连检验 “连连”表示连续性的相同事件的出现，表示连续性的相同事件的出现，“连连”的长度表示在的长度表示在“连连”中事件的个数。中事件的个数。 例如，对于例如，对于随机数列：随机数列：0.41, 0.68, 0.89, 0.7

51、4, 0.55, 0.36, 0.54, 0.72, 0.75, 0.08含含4个升降连（个升降连（+ + - - - + + + -），该升降连是用后面的数字与），该升降连是用后面的数字与前面的数字进行比较得到的。前面的数字进行比较得到的。 4个升降连（个升降连（+ + - - - + + + -）的长度分别为）的长度分别为2（因为有（因为有2个加号），个加号），3 （因为有（因为有3个减号）个减号） ，3 （因为有（因为有3个加号）个加号） ，1 （因为有（因为有1个减号）。个减号）。 在一个数列中，在一个数列中， “连连”的最小个数是的最小个数是1，即所有的数据是顺序上升，即所有的数据是

52、顺序上升，或是顺序下降的；或是顺序下降的； “连连” 的最大个数是的最大个数是n-1，n是是随机随机数的个数。数的个数。3.4 独立性检验 连贯性连贯性检验的基本思路是：把随机数列检验的基本思路是：把随机数列 按大小分按大小分成几类，考虑各类数字的出现是否有连贯的现象，即是否有连贯上升成几类，考虑各类数字的出现是否有连贯的现象，即是否有连贯上升或连贯下降的现象。或连贯下降的现象。nuuu,.,21当所要检验的数字总数超过当所要检验的数字总数超过20时，时，“连连”的总数的总数 T 近似服从正态分布，近似服从正态分布，即即其中，其中，),(2uNT9029162n312nu设设T为随机数序列所含

53、的连的总数，为随机数序列所含的连的总数，则则T 的均值和方差分别为（经验表的均值和方差分别为（经验表达式）：达式）：902916)(,312)(nTVarnTE其中，其中，n为随机数序列中数据的总数。为随机数序列中数据的总数。3.4 独立性检验为此为此 ，构造下列统计量：，构造下列统计量：90/)2916(3/)12(nnTZ 则统计量则统计量 Z 渐近服从渐近服从N(0,1)分布。由此，可利用统计量分布。由此，可利用统计量 Z 对随机数序对随机数序列的独立性进行检验。若显著水平为列的独立性进行检验。若显著水平为 ，查标准正态临界值表，查得，查标准正态临界值表，查得临界值临界值 ，则当下式成立

54、时，则当下式成立时，不能拒绝独立性的假设。不能拒绝独立性的假设。2/12/1ZZZ3.4 独立性检验2/1Z 例例3.8 对于水平对于水平 ，对下列，对下列40个随机数采用个随机数采用连贯性连贯性检验，检验，检验其独立性。检验其独立性。05.00.340.900.250.890.870.440.120.210.460.670.830.760.790.640.700.810.940.740.220.740.960.990.770.670.560.410.520.730.990.020.470.300.170.820.560.050.450.310.780.053.4 独立性检验解：该序列的升降连

55、如下解：该序列的升降连如下：+、-、+、-、-、-、+、+、+、+、-、+、-、+、+、+、-、-、+、+、+、-、-、-、-、+、+、+、-、+、-、-、+、-、-、+、-、+、- 这里共有这里共有22个连，即个连，即T=22 ，n=40，则由下式计算得则由下式计算得902916)(,312)(nTVarnTE则则6618.190/)2916(3/)12(nnTZ3.4 独立性检验3.4 独立性检验96.16618.1975.0ZZ得得故不能拒绝该数列的独立性假设。故不能拒绝该数列的独立性假设。0.000.050.060.070.080.090.00.50000.51990.52390.52

56、790.53190.53590.10.53980.55960.56350.56750.57140.57531.80.96400.96780.96860.96930.96990.97061.90.97130.97440.97500.97560.97620.97672.00.97730.97980.98030.98080.98120.98172/1Z对应于标准正态分布的临界表为对应于标准正态分布的临界表为：96.1975.0Z又2/13.4 独立性检验对于上述的标准正态分布，查的是双边临界对于上述的标准正态分布，查的是双边临界 ，其图形，其图形表示为：表示为：2/2/)(2/1nZ0)(2/1nZ2/1Z3.4 独立性检验3. 连贯性连贯性检验检验 有时，升降连检验并不能充分说明一组数据的独立性，此时可用有时，升降连检验并不能充分说明一组数据的独立性，此时可用正、负连检验。例如，下表所示的一组数据：正、负连检验。例如，下表所示的一组数据：（2.） 正、负连检验正、负连检验0.630.720.790.810.520.940.830.930.870.670.540.830.890.550.880.770.740.950.820.860.430.