2.2随机数与伪随机数 教列可以分为三种不同的类觌 真随机数列,随机数列,伪随机薮列 一、真随机数 亮随机教数列是不可预计的,因而也不可能量复产生 两个相同的真随机数数列。 ●亮随机數只能用棊些随机物理过程來产生。例如:放 射性衰变、电子设备的热噪音、守宙射绕的触发时间 如果采用随机物理尅程来产生象特卡洛计犷用的随机 数,理论上不存在什么问题。但在实际疝用时,要做 出速度很快(例如每秒产生上百个浮点数),而又准确 的随机数物理过程产生器是非常困难的。 弗里官雷欧( Frigerio)普人的真随机数获取: 用一个a粒子放射源和一个高分辫率的计教器敵成的 装量,在20毫秒时间内平均记录了24.315个a粒子。当计 数为偶数时,便在礅带上记录二选制的“1” 这个溦置每小时可以产生大约6000个31比啥(bits)的 真隨机数。这些教被存儲在礅带上,并遭过了一系列的“隨 机数”检驗后用于蒙特卡洛计算当中。 消除昏教计数的几率并不犄确等于1/2所引起的鎏的
2.2 随机数与伪随机数 数列可以分为三种不同的类型： 真随机数列，准随机数列, 伪随机数列 一、 真随机数 z 真随机数数列是不可预计的，因而也不可能重复产生 两个相同的真随机数数列。 z 真随机数只能用某些随机物理过程来产生。例如：放 射性衰变、电子设备的热噪音、宇宙射线的触发时间 等等。 z 如果采用随机物理过程来产生蒙特卡洛计算用的随机 数，理论上不存在什么问题。但在实际应用时，要做 出速度很快（例如每秒产生上百个浮点数），而又准确 的随机数物理过程产生器是非常困难的。 弗里吉雷欧(Frigerio)等人的真随机数获取： 用一个α 粒子放射源和一个高分辨率的计数器做成的 装置，在 20 毫秒时间内平均记录了 24.315 个α 粒子。当计 数为偶数时，便在磁带上记录二进制的“1” 。 这个装置每小时可以产生大约 6000 个 31 比特(bits)的 真随机数。这些数被存储在磁带上，并通过了一系列的“随 机数”检验后用于蒙特卡洛计算当中。 消除奇数计数的几率并不精确等于 1/2 所引起的偏差的 1
处理方法 利用上面介绍的装量得到的“0”或者“1”的真随机教 序列中,0和1出现的几率P(0)和P(1)可能并不赞确普于 1/2 我们从原始的真随机教序列出发。将序列中的二选制数 依次成对组合;如果这组中的两个数相同,则會去这两个数; 如果这组中的两个数不相同,则保留第二个二进制数而丢弃 第一个数。 这样杓成的一个新序列可以保证:在原始序列中的教是 相互独立的况下,“0”和“1”出现的概率相等 这一点可以从如下的计算中看出:“0”出现在新序列中 的概率为P(0)=P(P0)。这是因为新序列中的“0”只能在原 始序列中“1”后面跟“0”时才出现。同样“1”在新序 列中出现的概率P()=P(0)P()。因而无论p(0)和p()等于什么 值,p()和p(1)都相。由于在构成新序列时,會去了一组数 的几率为P2(0)+P(),因而P()+P(不普于1,而小于或普 于1/2。在这种方法中,对两个数不相同的一组数至少要丢 掉一个二进制数。很明显,它的广生效率为P(0)P()=P(-P), 其中P为P(0)或p(1)。其产生效率的最大值为25% 巴夫昂投针舆验在真随机教产生器中由于物理偏所 引起的问题: (1)在投针实验中平行线间间距必须保证为一个常数
处理方法： 利用上面介绍的装置得到的“0”或者“1”的真随机数 序列中，0 和 1 出现的几率 P(0)和 P(1)可能并不精确等于 1/2。 我们从原始的真随机数序列出发，将序列中的二进制数 依次成对组合；如果这组中的两个数相同，则舍去这两个数； 如果这组中的两个数不相同，则保留第二个二进制数而丢弃 第一个数。 这样构成的一个新序列可以保证：在原始序列中的数是 相互独立的情况下，“0”和“1”出现的概率相等。 这一点可以从如下的计算中看出：“0”出现在新序列中 的概率为 。这是因为新序列中的“0”只能在原 始序列中“1”后面跟着“0”时才出现。同样“1”在新序 列中出现的概率 P′( ) 0 = P(1)P(0) P′( ) 1 = P(0)P(1) p′(1) ( ) 0 (1) 2 2 P + P 。因而无论 和 等于什么 值，p 和 都相等。由于在构成新序列时，舍去了一组数 的几率为 ，因而 p(0) p(1) ′(0) P′(0) + P′(1)不等于 1，而小于或等 于 1/2。在这种方法中，对两个数不相同的一组数至少要丢 掉一个二进制数。很明显，它的产生效率为P(0) ( P 1) = P(1 − P)， 其中 p 为 p(0) 或 p(1) 。其产生效率的最大值为 25 %。 巴夫昂投针实验在真随机数产生器中由于物理偏差所 引起的问题： （1）在投针实验中平行线间间距必须保证为一个常数 2
值,外在所要求的误范国内与针长相普。如果我们仅耍求 丌的一至二位有效教事,这个要求是不难演足做到的,但 是如果要歌多位的有效數宇,这就比較困了。 (2)正确地判断临界状态下的针与平行线的相交也非 易事。第三,们还必须保证针的投掷位量和角度的分布是 均訇分布的。为保证角度分布的均性,可以在投针的时候, 让针迅遠旋鞭,并采用非常平的、毫擦系数是各向同性的泉 (3)投针位量的分布决不是均訇分布的,而是在投掷 目周国服从高斯分布。在实际疝用中,我们必须由奥验 来决定这一分布兜度。并且要对它引患的偏敵类似于前窗 所述的由弗里言雷欧人所做的复杂修正。 准随机数 准随机教序列并不具有随机性,仅仅是咆用来处理问 题时能够;到正确结果。 渔随机教概念是来自如下的寡奥:对伪随机教来说,要 奥现其严格数学觉义上的随机性。在理论上是不可能的,在 实际砬用中也没有这个必要。关健是要保证“隨机”数数列 具有能产生出所卿要的绪的必娶性。例如,在多量积分 和大多數模拟研兇中,多维间的每个点成棋拟事例被认为 是相互独立的,而这些朿或事例的顺序则似乎外不量要
值，并在所要求的误差范围内与针长相等。如果我们仅要求 π 值的一至二位有效数字，这个要求是不难满足做到的，但 是如果要求更多位的有效数字，这就比较困难了。 （2）正确地判断临界状态下的针与平行线的相交也非 易事。第三，我们还必须保证针的投掷位置和角度的分布是 均匀分布的。为保证角度分布的均匀性，可以在投针的时候， 让针迅速旋转，并采用非常平的、摩擦系数是各向同性的桌 面。 （3）投针位置的分布决不是均匀分布的，而是在投掷 目标点周围服从高斯分布。在实际应用中，我们必须由实验 来决定这一分布宽度，并且要对它引起的偏差做类似于前面 所述的由弗里吉雷欧等人所做的复杂修正。 二、准随机数 准随机数序列并不具有随机性质，仅仅是它用来处理问 题时能够得到正确结果。 准随机数概念是来自如下的事实：对伪随机数来说，要 实现其严格数学意义上的随机性，在理论上是不可能的，在 实际应用中也没有这个必要。关键是要保证“随机”数数列 具有能产生出所需要的结果的必要特性。例如，在多重积分 和大多数模拟研究中，多维空间的每个点或模拟事例被认为 是相互独立的，而这些点或事例的顺序则似乎并不重要。因 3
而我们可以在大多教振η中。放心地量随机性的概念于不 顺。同样,我们也可以不考对基些分布均勻性的涨落程度。 事实上在许多情况下,超均訇的分布比真随机薮的均訇分布 更合乎际要。 事奥上。准Ω特卡洛是将象特卡洛方法处理问题的錐数 向高錐扩晨的方法。由此可见准象兮卡洛方法的理论与真象 饽卡洛的理论很接近。 三、伪随机数 实际庇用的随机数常都是過过棊些教学公式计犷而 产生的伪隨机數。这样的伪随机数从数学义上讲巳经一点 不是随杋的了。但是,只耍伪随机数能够通过随机数的一系 列的统计检验,敦们就可以把它過作真随机教而放心地 用。这样觉们就可以很经济地、量复地产生出随机数。 对物理问题的计犷机模拟所卿要的伪随机教应当足 如下的橄准: 理论上,要求伪随机数产生器具备以下特征:良好的统 计分布兮性、高效率的伪随机数产生、伪随机教产生的孴环 周期长。产生程序可移植性好和伪随机教可以量复产生。其 中灡足良好的统计性质是最量要的。 嶽而实际用的伪随机数产生程序还没有一个是十全 十莫的。因此镋们求产生出的伪随机教疝当能过尽可能
而我们可以在大多数运算中，放心地置随机性的概念于不 顾。同样，我们也可以不考虑对某些分布均匀性的涨落程度。 事实上在许多情况下，超均匀的分布比真随机数的均匀分布 更合乎实际需要。 事实上，准蒙特卡洛是将蒙特卡洛方法处理问题的维数 向高维扩展的方法。由此可见准蒙特卡洛方法的理论与真蒙 特卡洛的理论很接近。 三、 伪随机数 实际应用的随机数通常都是通过某些数学公式计算而 产生的伪随机数。这样的伪随机数从数学意义上讲已经一点 不是随机的了。但是，只要伪随机数能够通过随机数的一系 列的统计检验，我们就可以把它当作真随机数而放心地使 用。这样我们就可以很经济地、重复地产生出随机数。 对物理问题的计算机模拟所需要的伪随机数应当满足 如下的标准： 理论上，要求伪随机数产生器具备以下特征：良好的统 计分布特性、高效率的伪随机数产生、伪随机数产生的循环 周期长，产生程序可移植性好和伪随机数可以重复产生。其 中满足良好的统计性质是最重要的。 然而实际使用的伪随机数产生程序还没有一个是十全 十美的。因此我们要求产生出的伪随机数应当能通过尽可能 4
多的统讣检验,以便人仉放心地使用。 1.伪随机数的产生方法 囟随机欻产生器产生的实上是伪随机数序列。 最基本的产生器是均訇分布的伪随机数产生器。 最早的伪随机教产生器可能是冯·诺曼平方取中法:该 方法首先给出一个2r做的数。取它的中间的r位教码作为 第一个伪随机数;然后将第一个伪隨机教平方构成一个新的 2r世教,再取中间的r世教作为第二个伪随机数.。如此 循环得到一个伪随机教序列。类似上述方法,利用十选制 公式袤示2r位数x的递推公式。 xm+=1o"xa mod 102r) AR=x, /10 这桦得到的伪随机数序列是分布在[0,1上的。相应的二 选制递推公式为(x为2r位二进制数) x2(mod 2 但是这种方法不是很好,现在已很少良用。这主要是因为该 方法产生的数列具有周期性,有些数(如零)甚至会紧接量 复出淝。 实际使用的伪随机数产生器常喲比平方取中法简单。如 今比校流行,并用得最多的是同余产生器。我仉过如下的 能性同关系式来产生教列
多的统计检验，以便人们放心地使用。 1． 伪随机数的产生方法 伪随机数产生器产生的实际上是伪随机数序列。 最基本的产生器是均匀分布的伪随机数产生器。 最早的伪随机数产生器可能是冯•诺曼平方取中法：该 方法首先给出一个 2r 位的数，取它的中间的 r 位数码作为 第一个伪随机数；然后将第一个伪随机数平方构成一个新的 2r 位数，再取中间的 r 位数作为第二个伪随机数…。如此 循环便得到一个伪随机数序列。类似上述方法，利用十进制 公式表示 2r 位数xn的递推公式。 [ ]( ) r n n r n r n x x x 2 2 2 1 /10 10 mod10 = = − + ξ . 这样得到的{ξ i}伪随机数序列是分布在[0，1]上的。相应的二 进制递推公式为( xn为 2r 位二进制数)： [ ]( ) r n n r n r n x x x 2 2 2 1 / 2 2 mod 2 = = − + ξ ， 但是这种方法不是很好，现在已很少使用。这主要是因为该 方法产生的数列具有周期性，有些数(如零)甚至会紧接着重 复出现。 实际使用的伪随机数产生器常常比平方取中法简单。如 今比较流行，并用得最多的是同余产生器。我们通过如下的 线性同余关系式来产生数列。 5
xrn+i=(ax, +c)(mod m) fn=xn/ 其中x称为种子,欧变它的值就讣到基本序列的不同区斆。 aC,x,m为大于零的查数,分别叫儆乘子、增量、初值和模。 使用时鼎要仔细地挑选模数m和乘子,使得产生出的伪随 机教的环周期要尽可能长。C≠0时能现最大的周期,但 是得到的伪隨机教的性不好。C≠0的这类情况称为混合同 氽发生器。通常选取x为任定非负数,子a和增量C取 如下彩式 C=2D+1 p和q为正蓬数。这爾种方法中的Pq,x0,m值的选择一舭是 通过定性分析和计算机试验来选择,使得到的随机教列具 有足够长的周期,而且独立性和均句性都能通过一系列的裣 对c=0的情况叫敵乘同佘油,由于减少了一个加法。因 而可以产生伪隨机数的遠度快些。这种方法产生的伪随机 教递推公式为 x mod m Sn =x/m x0,a,m也为正数,并分别叫做物值、乘子和模。 其他的产生伪隨机教的方法∶汎沌法伪杋數产生、反 馈移眚存器(RNG)-
， x m x ax c m n n n n / ( )(mod ) 1 = + = + ξ 其中 称为种子，改变它的值就得到基本序列的不同区段。 为大于零的整数，分别叫做乘子、增量、初值和模。 使用时需要仔细地挑选模数 和乘子 ，使得产生出的伪随 机数的循环周期要尽可能长。 0 x a,c, x0 ,m m a c ≠ 0时能实现最大的周期，但 是得到的伪随机数的特性不好。c ≠ 0的这类情况称为混合同 余发生器。通常选取 为任意非负整数，乘子 和增量 取 如下形式 0 x a c a = 4q +1 ， c = 2 p +1 . p 和 q 为正整数。这两种方法中的 值的选择一般是 通过定性分析和计算机试验来选择，使得到的伪随机数列具 有足够长的周期，而且独立性和均匀性都能通过一系列的检 验。 p, q, x0 , m 对c 的情况叫做乘同余法，由于减少了一个加法，因 而可以使产生伪随机数的速度快些。这种方法产生的伪随机 数递推公式为 = 0 ( ) x m x ax m n n n n / 1 mod = + = ξ ， x0 , a,m 也为正整数，并分别叫做初值、乘子和模。 其他的产生伪随机数的方法:混沌法伪随机数产生、反 馈移位寄存器（RNG）等。 6
2.伪随机教的統计检验 统讣裣验:均訇性检驗、独宀性检驗、組合親徫检驗、 无遠性检瞼、參数检验普尊。 最基本的是它的均訇性和抽立性的检验。 均勻性是指在[0,1]区域内葶长度区间的随机数分布的 个数应相。 独立性是抉先后顺序出的若千个随机教中,每一个数 的出親都和它前后的吝个数无关。 一个好的伪随机教序列除了能遢过这丌种主要的筑讣 检验外,还猾要能过别的多种检验。能过的检驗越多, 则该产生器就越优良可靠。 (1)均句性检驗一频率检验 均訇性裣验是所有检驗中最简单的一种。它的方法很多, 如x2方法。 设有在区间[0,1]上的伪随机数序列为512…5}如 果该伪隨机数是均勻分布的,则将[0,1]区间分成k个相等 的子区间后,落在每个子区间的伪随机教个教N应当近似为 N/k。此数也称频数。它的毓计误鑾σ=、=√Nk。統计量 x按定义应为 (N -N/k) N/k =∑(N-Nk)
2. 伪随机数的统计检验 统计检验: 均匀性检验、独立性检验、组合规律检验、 无连贯性检验、参数检验等等。 最基本的是它的均匀性和独立性的检验。 均匀性是指在[0，1]区域内等长度区间的随机数分布的 个数应相等。 独立性是按先后顺序出现的若干个随机数中，每一个数 的出现都和它前后的各个数无关。 一个好的伪随机数序列除了能通过这两种主要的统计 检验外，还需要能通过别的多种检验。能通过的检验越多， 则该产生器就越优良可靠。 （1） 均匀性检验—频率检验 均匀性检验是所有检验中最简单的一种。它的方法很多, 如 方法。 2 χ 设有在区间[0，1]上的伪随机数序列为{ξ1,ξ 2 ,......,ξ N } Ni 。如 果该伪随机数是均匀分布的，则将[0，1]区间分成 k 个相等 的子区间后，落在每个子区间的伪随机数个数 应当近似为 N / k 。此数也称频数。它的统计误差 N = N / k σ i = i 。统计量 χ2按定义应为 ( ) ( ) 2 1 1 2 2 / / / ∑ ∑ = − = − − = k i i k i i N N k N k N k N N k χ . 7
x2在此问题中应服从x2(k-1)的分布。据此可以假定一 个显着性水平值来进行检验。我们可以从x2查得(k-1)个 自由度的显水平为a时的1真。计算出来的x2小于ta, 则认为在a的显著水平下,原伪隨机数在[0,1区间是均 訇分布的假宠是正确的。 如果计算的得到的x2大于,则认为在a的显着水平 下,伪隨机数不灡兄均訇性的要求。 通常取显着水平为0.01或0.05。为了反映均勻性分 布的啥性,k的取值不宜太小,但也不能太大。一般选取 的k值。要能每个子区间有着干个伪随机数时就比校合 (2)独立性检验一元量复联列检验 如是把[0,1上的伪随机数序列{,2…,2}分成两列 2-12…2N-1 2:942 草一列作为随机变量x的取值,第二列作为随机变量y的取 值。在x-y平面内的单位正方形域0≤x10≤y≤]上,分别以 平行于坐标轴的平行。将正方形域分成k×k个相同面积的 小正方形网格。缮在每个网格内的机教的频数n应当近似 尊于N/k。由此可以算出x2为
在此问题中应服从 的分布。据此可以假定一 个显著性水平值来进行检验。我们可以从 表查得 个 自由度的显著水平为 2 χ ( 1) 2 χ k − 2 χ ( ) k −1 α 时的 值。计算出来的 小于t ， 则认为在 αt 2 χ α α 的显著水平下，原伪随机数在[0，1]区间是均 匀分布的假定是正确的。 如果计算的得到的χ2 大于tα，则认为在α 的显著水平 下，伪随机数不满足均匀性的要求。 通常取显著水平为 0.01 或 0.05。为了反映均匀性分 布的特性，k 的取值不宜太小，但也不能太大。一般选取 的 k 值，要能使每个子区间有若干个伪随机数时就比较合 适。 （2） 独立性检验—无重复联列检验 如果把[0，1]上的伪随机数序列{ξ1,ξ 2 ,......,ξ 2N }分成两列 1 3 2 1 2 1 , ,... ,..., ξ ξ ξ i− ξ N− 2 4 2i 2N ξ ,ξ ,...ξ ,...,ξ 第一列作为随机变量 的取值，第二列作为随机变量 的取 值。在 平面内的单位正方形域 x y x − y [0 ≤ x ≤1,0 ≤ y ≤1] k k 上，分别以 平行于坐标轴的平行线，将正方形域分成 × 个相同面积的 小正方形网格。落在每个网格内的随机数的频数 应当近似 等于 。由此可以算出 为 ij n 2 N k/ 2 χ 8
x2应满足z2(k-1)的分布。据此可以采用与均勻性检验的x2 方法,假定出显着性水平来选行检验。熃卯也可以把伪隨机 数序列分为三列、四列、…,用与上面所述相似的方法进行 多维独立性检验。 3.独立于计算机机型的伪随机教产生器 在实际应用中,我们常常希望使用能够在各种型号的计 犷机上工作,并能量复产生相同伪随机数序列的产生器。 这种产生器的实现是基于如下的思觌:如果要产生[0,1] 区间的伪随机浮点数,选择贛度最低的计机作为标准糖 度,而对字长較长的计η机,用将較低的藪位人为置粵的方 法,即在高贛度的计算机上选行低精度的运箕。 这样的伪随机教产生器无论从伪蓖机教的量复周期和 产生伪随机教的滾度部不犷理翘。但它却可以在大多数的计 犷机上工作。 这些伪随机数产生器产生的劢几个数近似为 R1=0.10791504.R2=0.58747506 FUNCTION RN32 (IDUMMY) C CDC VERSioN F. JAMES, 1978 C IY IS THE SEED. CONS=2**-31
2 2 2 2 , 1 k ij i j k N n N k χ = = − ∑ . 2 χ 应满足 (( ) ) 2 2 χ k − 1 的分布。据此可以采用与均匀性检验的 方法，假定出显著性水平来进行检验。我们也可以把伪随机 数序列分为三列、四列、…，用与上面所述相似的方法进行 多维独立性检验。 2 χ 3. 独立于计算机机型的伪随机数产生器 在实际应用中，我们常常希望使用能够在各种型号的计 算机上工作，并能重复产生相同伪随机数序列的产生器。 这种产生器的实现是基于如下的思想：如果要产生[0,1] 区间的伪随机浮点数，选择精度最低的计算机作为标准精 度，而对字长较长的计算机，用将较低的数位人为置零的方 法，即在高精度的计算机上进行较低精度的运算。 这样的伪随机数产生器无论从伪随机数的重复周期和 产生伪随机数的速度都不算理想，但它却可以在大多数的计 算机上工作。 这些伪随机数产生器产生的前几个数近似为： R1=0.10791504…，R2=0.58747506…。 FUNCTION RN32(IDUMMY) C CDC VERSION F.JAMES, 1978 C IY IS THE SEED. CONS=2**-31 9
DATA IY/ 65539/ DATA CONS/1661400000000000 DATA MASK31/177777777 IY=IY*69069 C KEEP ONLY loWeR 31 BITS IY=IY AND, MASK31 C Set lOWER 8 BITS TO ZERO TO ASSURE EXACT FLOat IY=IY.AND.07777777777777777400B YFL=JY RN32=YFL米CONS RETURN C ENTRY TO INPUT SEED ENTRY RN32IN IYEIDUMMY RETURN C ENTRY TO OUTPUT SEED ENTRY RN32OT IDUMMYEIY RETURN END FUNCTION RN32 ( DUMMY)
DATA IY/65539/ DATA CONS/16614000000000000000B/ DATA MASK31/17777777777B/ IY=IY*69069 C KEEP ONLY LOWER 31 BITS IY=IY.AND.MASK31 C SET LOWER 8 BITS TO ZERO TO ASSURE EXACT FLOAT. IY=IY.AND.07777777777777777400B YFL=JY RN32=YFL*CONS RETURN C ENTRY TO INPUT SEED ENTRY RN32IN IY=IDUMMY RETURN C ENTRY TO OUTPUT SEED ENTRY RN32OT IDUMMY=IY RETURN END FUNCTION RN32(DUMMY) 10