2.2随机数与伪随机数

《2.2随机数与伪随机数》由会员分享，可在线阅读，更多相关《2.2随机数与伪随机数（12页珍藏版）》请在金锄头文库上搜索。

1、 2.2 随机数与伪随机数 2.2 随机数与伪随机数 数列可以分为三种不同的类型： 数列可以分为三种不同的类型： 真随机数列，准随机数列, 伪随机数列真随机数列，准随机数列, 伪随机数列 一、 真随机数 一、 真随机数 ? 真随机数数列是不可预计的，因而也不可能重复产生两个相同的真随机数数列。 真随机数数列是不可预计的，因而也不可能重复产生两个相同的真随机数数列。 ? 真随机数只能用某些随机物理过程来产生。例如：放射性衰变、电子设备的热噪音、宇宙射线的触发时间等等。 真随机数只能用某些随机物理过程来产生。例如：放射性衰变、电子设备的热噪音、宇宙射线的触发时间等等。 ? 如果采用随机物理过程来产

2、生蒙特卡洛计算用的随机数，理论上不存在什么问题。但在实际应用时，要做出速度很快（例如每秒产生上百个浮点数） ，而又准确的随机数物理过程产生器是非常困难的。 如果采用随机物理过程来产生蒙特卡洛计算用的随机数，理论上不存在什么问题。但在实际应用时，要做出速度很快（例如每秒产生上百个浮点数） ，而又准确的随机数物理过程产生器是非常困难的。 弗里吉雷欧(Frigerio)等人的真随机数获取： 弗里吉雷欧(Frigerio)等人的真随机数获取： 用一个用一个粒子放射源和一个高分辨率的计数器做成的装置，在 20 毫秒时间内平均记录了 24.315 个粒子放射源和一个高分辨率的计数器做成的装置，在 20 毫

3、秒时间内平均记录了 24.315 个粒子。当计数为偶数时，便在磁带上记录二进制的“1” 。 粒子。当计数为偶数时，便在磁带上记录二进制的“1” 。 这个装置每小时可以产生大约 6000 个 31 比特(bits)的真随机数。这些数被存储在磁带上，并通过了一系列的“随机数”检验后用于蒙特卡洛计算当中。 这个装置每小时可以产生大约 6000 个 31 比特(bits)的真随机数。这些数被存储在磁带上，并通过了一系列的“随机数”检验后用于蒙特卡洛计算当中。 消除奇数计数的几率并不精确等于1/2所引起的偏差的消除奇数计数的几率并不精确等于1/2所引起的偏差的1处理方法： 处理方法： 利用上面介绍的装置

4、得到的“0”或者“1”的真随机数序列中，0 和 1 出现的几率 P(0)和 P(1)可能并不精确等于1/2。 利用上面介绍的装置得到的“0”或者“1”的真随机数序列中，0 和 1 出现的几率 P(0)和 P(1)可能并不精确等于1/2。 我们从原始的真随机数序列出发，将序列中的二进制数依次成对组合； 如果这组中的两个数相同， 则舍去这两个数；如果这组中的两个数不相同，则保留第二个二进制数而丢弃第一个数。 我们从原始的真随机数序列出发，将序列中的二进制数依次成对组合； 如果这组中的两个数相同， 则舍去这两个数；如果这组中的两个数不相同，则保留第二个二进制数而丢弃第一个数。 这样构成的一个新序列可

5、以保证：在原始序列中的数是相互独立的情况下， “0”和“1”出现的概率相等。 这样构成的一个新序列可以保证：在原始序列中的数是相互独立的情况下， “0”和“1”出现的概率相等。 这一点可以从如下的计算中看出： “0”出现在新序列中的概率为。这是因为新序列中的“0”只能在原始序列中“1”后面跟着“0”时才出现。同样“1”在新序列中出现的概率这一点可以从如下的计算中看出： “0”出现在新序列中的概率为。这是因为新序列中的“0”只能在原始序列中“1”后面跟着“0”时才出现。同样“1”在新序列中出现的概率( )( ) ( )010PPP=( )( ) ( )10 PP1P=) 1 (p( )( )10

6、22PP+。因而无论和等于什么值，。因而无论和等于什么值，p和都相等。由于在构成新序列时，舍去了一组数的几率为，因而和都相等。由于在构成新序列时，舍去了一组数的几率为，因而)0(p) 1 (p)0( ( )( )10PP+不等于 1，而小于或等于 1/2。在这种方法中，对两个数不相同的一组数至少要丢掉一个二进制数。 很明显， 它的产生效率为不等于 1，而小于或等于 1/2。在这种方法中，对两个数不相同的一组数至少要丢掉一个二进制数。 很明显， 它的产生效率为( ) ( )P=1()PP10P，其中，其中p为或。其产生效率的最大值为 25 %。 为或。其产生效率的最大值为 25 %。 )0(p)

7、 1 (p巴夫昂投针实验在真随机数产生器中由于物理偏差所引起的问题： 巴夫昂投针实验在真随机数产生器中由于物理偏差所引起的问题： （1）在投针实验中平行线间间距必须保证为一个常数（1）在投针实验中平行线间间距必须保证为一个常数2值，并在所要求的误差范围内与针长相等。如果我们仅要求值，并在所要求的误差范围内与针长相等。如果我们仅要求值的一至二位有效数字，这个要求是不难满足做到的，但是如果要求更多位的有效数字，这就比较困难了。 值的一至二位有效数字，这个要求是不难满足做到的，但是如果要求更多位的有效数字，这就比较困难了。 （2）正确地判断临界状态下的针与平行线的相交也非易事。第三，我们还必须保证针

8、的投掷位置和角度的分布是均匀分布的。 为保证角度分布的均匀性， 可以在投针的时候，让针迅速旋转，并采用非常平的、摩擦系数是各向同性的桌面。 （2）正确地判断临界状态下的针与平行线的相交也非易事。第三，我们还必须保证针的投掷位置和角度的分布是均匀分布的。 为保证角度分布的均匀性， 可以在投针的时候，让针迅速旋转，并采用非常平的、摩擦系数是各向同性的桌面。 （3）投针位置的分布决不是均匀分布的，而是在投掷目标点周围服从高斯分布。在实际应用中，我们必须由实验来决定这一分布宽度，并且要对它引起的偏差做类似于前面所述的由弗里吉雷欧等人所做的复杂修正。 （3）投针位置的分布决不是均匀分布的，而是在投掷目标

9、点周围服从高斯分布。在实际应用中，我们必须由实验来决定这一分布宽度，并且要对它引起的偏差做类似于前面所述的由弗里吉雷欧等人所做的复杂修正。 二、准随机数 二、准随机数 准随机数序列并不具有随机性质，仅仅是它用来处理问题时能够得到正确结果。 准随机数序列并不具有随机性质，仅仅是它用来处理问题时能够得到正确结果。 准随机数概念是来自如下的事实：对伪随机数来说，要实现其严格数学意义上的随机性，在理论上是不可能的，在实际应用中也没有这个必要。关键是要保证“随机”数数列具有能产生出所需要的结果的必要特性。例如，在多重积分和大多数模拟研究中，多维空间的每个点或模拟事例被认为是相互独立的，而这些点或事例的顺

10、序则似乎并不重要。因准随机数概念是来自如下的事实：对伪随机数来说，要实现其严格数学意义上的随机性，在理论上是不可能的，在实际应用中也没有这个必要。关键是要保证“随机”数数列具有能产生出所需要的结果的必要特性。例如，在多重积分和大多数模拟研究中，多维空间的每个点或模拟事例被认为是相互独立的，而这些点或事例的顺序则似乎并不重要。因3而我们可以在大多数运算中，放心地置随机性的概念于不顾。 同样， 我们也可以不考虑对某些分布均匀性的涨落程度。事实上在许多情况下，超均匀的分布比真随机数的均匀分布更合乎实际需要。 而我们可以在大多数运算中，放心地置随机性的概念于不顾。 同样， 我们也可以不考虑对某些分布均

11、匀性的涨落程度。事实上在许多情况下，超均匀的分布比真随机数的均匀分布更合乎实际需要。 事实上，准蒙特卡洛是将蒙特卡洛方法处理问题的维数向高维扩展的方法。由此可见准蒙特卡洛方法的理论与真蒙特卡洛的理论很接近。 事实上，准蒙特卡洛是将蒙特卡洛方法处理问题的维数向高维扩展的方法。由此可见准蒙特卡洛方法的理论与真蒙特卡洛的理论很接近。 三、 伪随机数 三、 伪随机数 实际应用的随机数通常都是通过某些数学公式计算而产生的伪随机数。这样的伪随机数从数学意义上讲已经一点不是随机的了。但是，只要伪随机数能够通过随机数的一系列的统计检验，我们就可以把它当作真随机数而放心地使用。这样我们就可以很经济地、重复地产生

12、出随机数。 实际应用的随机数通常都是通过某些数学公式计算而产生的伪随机数。这样的伪随机数从数学意义上讲已经一点不是随机的了。但是，只要伪随机数能够通过随机数的一系列的统计检验，我们就可以把它当作真随机数而放心地使用。这样我们就可以很经济地、重复地产生出随机数。 对物理问题的计算机模拟所需要的伪随机数应当满足如下的标准： 对物理问题的计算机模拟所需要的伪随机数应当满足如下的标准： 理论上，要求伪随机数产生器具备以下特征：良好的统计分布特性、高效率的伪随机数产生、伪随机数产生的循环周期长，产生程序可移植性好和伪随机数可以重复产生。其中满足良好的统计性质是最重要的。 理论上，要求伪随机数产生器具备以

13、下特征：良好的统计分布特性、高效率的伪随机数产生、伪随机数产生的循环周期长，产生程序可移植性好和伪随机数可以重复产生。其中满足良好的统计性质是最重要的。 然而实际使用的伪随机数产生程序还没有一个是十全十美的。因此我们要求产生出的伪随机数应当能通过尽可能然而实际使用的伪随机数产生程序还没有一个是十全十美的。因此我们要求产生出的伪随机数应当能通过尽可能4多的统计检验，以便人们放心地使用。 多的统计检验，以便人们放心地使用。 1 伪随机数的产生方法 1 伪随机数的产生方法 伪随机数产生器产生的实际上是伪随机数序列。 伪随机数产生器产生的实际上是伪随机数序列。 最基本的产生器是均匀分布的伪随机数产生器

14、。 最基本的产生器是均匀分布的伪随机数产生器。 最早的伪随机数产生器可能是最早的伪随机数产生器可能是冯冯诺曼平方取中法诺曼平方取中法：该方法首先给出一个 2r 位的数，取它的中间的 r 位数码作为第一个伪随机数；然后将第一个伪随机数平方构成一个新的2r 位数，再取中间的 r 位数作为第二个伪随机数：该方法首先给出一个 2r 位的数，取它的中间的 r 位数码作为第一个伪随机数；然后将第一个伪随机数平方构成一个新的2r 位数，再取中间的 r 位数作为第二个伪随机数。如此循环便得到一个伪随机数序列。类似上述方法，利用十进制公式表示 2r 位数的递推公式。 。如此循环便得到一个伪随机数序列。类似上述方

15、法，利用十进制公式表示 2r 位数的递推公式。 nx()r nnr nr n xxx222 1 10/10mod10= + . . 这样得到的这样得到的 i伪随机数序列是分布在0，1上的。相应的二进制递推公式为(为 2r 位二进制数)： 伪随机数序列是分布在0，1上的。相应的二进制递推公式为(为 2r 位二进制数)： nx()r nnr nr n xxx222 1 2/2mod2= + ， ， 但是这种方法不是很好，现在已很少使用。这主要是因为该方法产生的数列具有周期性，有些数(如零)甚至会紧接着重复出现。 但是这种方法不是很好，现在已很少使用。这主要是因为该方法产生的数列具有周期性，有些数(

16、如零)甚至会紧接着重复出现。 实际使用的伪随机数产生器常常比平方取中法简单。如今比较流行，并用得最多的是同余产生器。我们通过如下的实际使用的伪随机数产生器常常比平方取中法简单。如今比较流行，并用得最多的是同余产生器。我们通过如下的线性同余关系式线性同余关系式来产生数列。 来产生数列。 5， ， mxmcaxxnnnn /)(mod(1 =+=+ 其中称为种子，改变它的值就得到基本序列的不同区段。为大于零的整数，分别叫做其中称为种子，改变它的值就得到基本序列的不同区段。为大于零的整数，分别叫做乘子、增量、初值乘子、增量、初值和和模模。使用时需要仔细地挑选模数和乘子，使得产生出的伪随机数的循环周期要尽可能长。使用时需要仔细地挑选模数和乘子，使得产生出的伪随机数的循环周期要尽可能长。0xm,0xca ,ma0c时能实现最大的周期，但是得到的伪随机数的特性不好。时能实现最大的周期，但是得到的伪随机数的特性不好。0c的这类情况称为的这类情况称为混合同余发生器混合同余发生器。通常选取为任意非负整数，