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