第五章 蒙特卡罗方法与随机数

第五章蒙特卡罗方法与随机数

第五章蒙特卡罗方法与随机数

蒙特卡罗（MonteCarlo）方法，又称随机抽样法或统计实验法，是基于对概率模型的观察或抽样试验得到问题近似解的方法。本章讨论：

1、蒙特卡罗方法的基本思想；

2、随机数的产生和检验。

蒙特卡罗（Monte-Carlo）方法

蒙特卡罗方法以概率统计理论为其主要理论基础，以随机抽样为主要手段。先建立一个概率模型或随机过程，使它的参数等于问题的解；然后通过对模型或过程的观察或抽样试验来计算所求随机参数计算所求随机参数的统计特征，最后给出所求解的近似值。

若射击弹着点到靶心的距离r，则得分为Y，Y与r的关系为g(r)，即

r用统计试验的方法求其数学期望

N次射击的弹着点股票价格的预测研究

（ITO）过程

维纳过程（Wienerprocess）

服从正态分布

σ＝0.03，Δt=0.01,股票的初始值S=30元，用变换

每周期开始价随机样本v1∈N(0,1)随机样本v2股价变化ΔS每周期结束价30.000-0.12675-0.0026-0.0780829.92229.9220.7216090.0228480.68366430.60630.606-1.08988-0.0315-0.9639729.64229.642-0.60426-0.01693-0.5017729.14029.1401.9316120.0591481.72357530.86330.863-0.12521-0.00256-0.078930.78530.785-1.266-0.03678-1.1322629.65229.6521.5679780.0482391.43040631.08331.083-0.26258-0.00668-0.2075630.87530.8750.0898150.0038940.12024230.99530.9951.0504160.0327121.01393632.009（1）构造或描述概率过程。（2）实现抽样。（3）建立估计量。实施蒙特卡罗仿真的主要步骤：蒙特卡罗仿真的优点：（1）收敛速度与问题的维数无关。（2）受问题的条件限制的影响小。（3）程序结构简单、清晰，便于编制和调试。（4）对于一些物理问题，具有其它数值方法不能替代的作用。随机数的生成和检验

随机数就是按随机方法而生成的数码。即0，1，2……9这十个数字出现的机会等概率，排列的顺序随机。均匀分布随机数随机数的产生方法0123468932765140675454324678568087586545均匀分布随机数f(x)F(x)xx1010111

均匀分布概率密度及分布函数

随机抽取等概且服从均匀分布的小数（从0到1，但不包括1）称为均匀随机数

产生均匀分布随机数方法

手工方法2.随机数表

物理方法4.数学方法

手工方法掷骰子、抽签、发纸牌或从“搅拌均匀的容器”中模编号球的方法等，但效率很低。随机数表物理方法对随机数表法的一种改进办法是在计算机上装一台物理随机数发生器，把具有随机性质的物理过程（如以放射性物质为随机源），在计算机上直接转换成随机数字。这种方法虽然产生了随机数，但无可追溯性。由此得到的随机数一去不返，不能重复出现，因此无法再用原来的随机数试算或检查。又因为对设备的要求较高，而实用价值较低

数学方法利用数学递推公式，在计算机上产生随机数，是目前使用较广、发展较快的一种方法。由于这种方法产生的数，只能近似地具备随机性质，因此称为伪随机数（pseudorandomnumber）。产生伪随机数的方法

（一）历史上曾经采用过的方法1.平方取中法(mid-squaremethod)

平方取中法计算简单，但有明显得缺点，一是无法说明用什么样的种子数可保证有足够长的周期，二是容易退化到某一常数或零，而一旦有一个零，则以后的数全为零以21为初始种子数，用平方取中法求随机数。xixi2xi+1ui21449364986300441193686494096008100640036000900004493649863000.440.930.640.090.080.060.030.000.002.乘法取中法(mid-productmethod）

设初始种子为12和34，用乘法取中法求随机数。xixi•xi+1xi+1ui1234403644585519472100408136014491584255231901045007600280014000200004036445855194721000.400.360.440.580.550.190.040.070.020.010.000.003.常数乘子法（constantmultipliermethod）

常数乘子法的周期较长，均匀分布特性较好，但仍有平方取中和乘法取中的缺点——容易退化。同时，成功与否取决于所选常数。xiki•xixi+1ui341870870.87874785780.78784290290.29291595590.59593245240.24241320320.32321760760.76764180180.1818990990.99995445440.44442420420.42422310310.31311705700.07703850850.85854675670.67673685680.68683740740.7474407070.07341870870.87874785780.78选择常数k=55，初始种子数为34，用常数乘子法求随机数。

（二）线性同余法1.混合线性同余法

2.乘法线性同余法3.二次同余法

4.加法同余法

用线性同余、混合线性同余、二次同余及加法同余，计算随机数。其中：a=21，b=59，c=11；模m=128；种子数是：x0

=34,x-1

=51。参数m，a，c满足条件：①m与c互素；②如果q是m的一个素因子，则q也是a-l的因子；③如果m能被4整除，则a-1也能被4整除。通常取m=2b,c为奇数，而a-1可被4整除，可得到满周期。随机数的检验

由于计算机产生的随机数，是按某一迭代公式计算出来的，因此实际上由此而得的数列是确定性而不是随机的。为此，通常要对随机数进行测试，观察它与均匀分布U(0,1)的类似程度。随机数检验可分为:参数检验均匀性检验独立性检验

检验随机数的均值、二阶矩及方差等估计量与均匀分布U(0,1)的理论值有无显著差别

参数检验用参数检验由某随机数发生器生成的100个随机数的均匀性。

0.38200.10070.59650.89910.88460.95850.01450.40740.86320.13860.24500.04550.03240.16410.21960.01710.28500.34310.55360.35740.37180.35560.91030.46600.42620.30390.97570.80670.99120.25630.95170.05340.70500.81650.97250.46630.30020.75020.35150.77570.07430.19840.06410.35830.48700.51120.37350.98590.04070.23070.00500.92610.10030.25670.77570.67960.80910.72430.08510.13230.75620.62650.17370.40480.55230.71150.55520.18120.97030.68690.52880.79670.80570.26220.17800.86680.11480.05950.76160.73840.98630.92560.90390.54500.50080.67500.48980.14580.03800.79630.67160.73170.58450.15220.89220.37780.20050.20580.33400.3251

检验随机数在各子区间的频率与理论值N/n有无显著差异。常用的检验方法有:频率检验（拟合优度检验）

累积频率检验（柯尔莫哥洛夫－斯米尔诺夫检验）

均匀性检验频率检验是按以下方法，对随机数独立且服从U(0,1)分布的假设作显著性检验。具体步骤是：①将区间[0,1]分成k个不相交的等长子区间②计算经验频数③计算统计量④判断统计量χ2是否小于临界值在5％的显著性水平上，用χ

2检验所给的100个随机数的均匀性。将区间[0,1]分成10个等间距的子区间，各子区间的随机数个数ni

如表4.2.5:

经验频数表子区间i12345678910

ni121291379512912据表的经验频数计算统计量χ2

χ2＝6.2<16.92

累积频率检验又称柯尔莫哥洛夫－斯米尔诺夫检验，是连续分布的拟合性检验（简称K-S检验）。按以下步骤对样本的经验分布函数Fn(x)与总体分布函数F(x)进行显著性检验。

①将随机数按大小顺序排列成u(1)，u(2)，…，u(n)，并计算随机数的经验分布函数Fn(x)②计算

③计算统计量④根据显著性水平α及样本大小n查K-S表检索临界值⑤比较统计量D及临界值

【例4.2.7】在5％的显著性水平，用K-S法检验例4.2.5前10个随机数的均匀性。解：将随机数按大小顺序排列，得相关数据如表

Dn+=0.161,D-n=0.263，

Dn=max{0.161,0.263}=0.263

D0.05(10)=0.41

i12345678910u(i)0.0150.1010.1390.3820.4070.5970.8630.8850.8990.959i/n0.10.20.30.40.50.60.70.80.91.0i/n-u(i)0.0850.0990.1610.0180.0930.003-0.163-0.0850.0010.041u(i)-(i-1)/n0.0150.001-0.0610.0820.0070.0970.2630.1850.0990.059

独立性检验就是检查一个序列的随机数之间是否存在相关性。常用检验的方法有：自相关检验

组合规律检验

连贯性检验

独立性检验

利用自相关系数值的大小来判断随机数的独立性，因此也称相关系数检验。具体步骤是：

①计算j阶自相关系数的估计值

②构造统计量vj（j=1，2，…，m）

③根据显著性水平α，比较zα/2和统计量判断待检随机数是否具有独立性。

>zα/则拒绝相关系数ρj=0的假设

自相关检验

通常用扑克检验（pokertest）检验样本中重复出现数字的频率，从而检查其组合规律性。

组合规律检验

若Ak为随机数中有且仅有k个数字相同的事件，Ak出现的频数为mk。则三种可能事件发生的理论频数为μk=nPk。构造统计量

由于统计量χ2渐近服从χ2(2)分布。因此可利用χ2分布检验随机数列的组合规律性来判断其独立性。å=-=3122)(kkkkmmmc有1000个用三位小数表示的随机数，经过统计知有680个三位数都不相同，289个恰有两位数字相同，31个三位数字都相同。试检验这些数据是否相互独立。解：三种不同组合情况的有关数据如下：据此计算统计量,若显著性水平α＝0.05，查分布表得，因为＝47.66>5.991，拒绝符合组合规律，表明这1000个随机数不独立。类型概率观测频数mk

理论频数μk

A10.7268072016002.22A20.272892703611.34A30.01311044144.1连贯性检验通过考察数字的排列来检验随机数独立性假设，即检验随机数列先后出现的随机性，重点是检验其连贯现象是否异常，从而判断这些数据是否独立。连贯检验可分为：1、升降连检验2、正负连检验。升降连检验由u1，u2，…，un，构造数列{vi}，vi＝ui-ui-1(i=2,3,…,n)，根据数列{vi}的符号，分成升降两类连，vi连续为正的连称为升连，vi连续为的连称为降连。用连来表示随机数增减及其长度的变化规律的方法称为升降连检验。ui0.7440.9060.2640.2310.2570.0070.1590.3630.7140.070Vi0.162-0.642-0.0330.026-0.2500.1520.2040.351-0.644+--+-+++-ui0.3690.2680.8980.13620.0860.4730.7080.2450.4380.132vi0.299-0.1010.630-0.762-0.0500.3870.236-0.4630.193-0.306+-+--++-+-ui0.4420.2270.49390.5810.6240.5980.7450.8060.6180.703vi0.310-0.2150.2670.0870.043-0.0270.1480.061-0.1880.085+-+++-++-+ui0.2740.5580.47430.1630.4350.9830.1970.6360.6400.530vi-0.4290.284-0.084-0.3110.2720.548-0.7860.4390.004-0.110-+--++-++-ui0.4390.4090.94630.9740.7160.0640.7910.7110.5520.496vi-0.091-0.0300.5380.027-0.258-0.6520.727-0.080-0.159-0.056--++--+---{vi}及升降连升连、降连共32个,其中长度为1的有19个,长度为2的有9个,长度为3的有4个T=32，n=50，统计量

又zα/2＝z0.025=1.96，可见|Z|<z0.025，所以不能拒绝独立性假设。正负连检验正负连是将数值在均值以上的标以“＋”，表示正连；在均值以下的标以“－”，表示负连。然后，用类似升降连检验的方法进行检验。

假设n1和n2分别是在均值以上和以下的数据个数，T为连的总数，其均值和方差分别是

，

（5.3.11）当n1或n2大于20时，T近似服从正态分布，统计量

（5.3.12）服从标准正态分布N(0,1)。同样地，给定显著性水平α，若|Z|≤zα/2，则不拒绝独立性的假设。

显著性水平α＝5％，用正负连法检验上例所给的随机数列的独立性。ui0.7440.9060.2640.2310.2570.0070.1580.3630.7140.070vi0.2580.420-0.222-0.255-0.229-0.479-0.327-0.1230.228-0.416符号++------++ui0.3690.2680.8980.1360.0860.4730.7080.2450.4380.132vi-0.117-0.2180.412-0.350-0.400-0.0130.222-0.241-0.048-0.354符号--+-