第七章概率方法课件

VII、概率方法7.1随机数生成7.2MonteCarlo方法7.3减小方差的方法7.4拟MonteCarlo方法7.5在优化中的应用2024/7/1317.1随机数生成 伪随机数生成方法生成方法有多种方法，最常用的是：线性同馀序列逆乘同馀法Tausworthe序列通常，对应生成多项式是本原多项式。生成U0，1分布对前两种：r=f(x)/N对Tausworthe序列：r=x/2k+12024/7/132随机数生成随机数生成lIBMRANDU取值：a=216+3b=0N=231x0=1l俄国一40位机：a=517b=0N=240 x0=1lIS95中的超长地址码为周期，其生成多项式l基站地址码：l同相：l正交：基站地址码：基站地址码：2024/7/133离散随机变量抽样离散随机变量抽样设变量以概率P1，P2，,Pn分别取值a1，a2，,an，即其中，2024/7/134离散随机变量抽样离散随机变量抽样算法：取则由随机数序列中依次选取随机数，求满足检验条件的k值。这时得到变量的取样值为2024/7/135POISSON分布对于一些特殊的离散分布，几何，二项，超几何及POISSON分布，可从它们的概率意义出发得到一些直接的抽样方法。例：POISSON分布对随机序列，求满足下面条件的k：2024/7/136连续分布抽样最直接的方法：通过分布函数的逆的方法如果所要做的分布为，其概率分布函数为，则假定为随机数，对应的满足分布为。舍选抽样法设为任意的二维分布密度函数，为任意的函数，则对于如下形式的分布2024/7/137舍选抽样则有如下抽样形式抽样效率为2024/7/138例1例：是（0，1）上以为密度函数的随机变量，其中L=sup f（x），取有限值dogeneratewhile()return抽样效率为LO1y=f(x)P1P2yx2024/7/139例2例：产生密度函数为下面分布的随机变量直接法：考虑到有随机数的对称性2024/7/1310例3例：产生指数分布的随机变量直接法：求得反函数为因为r与1-r同分布，所以2024/7/1311正态分布抽样取随机变数，利用二元函数变换得到两个相互独立的正态分布解方程得到：于是2024/7/1312正态分布（2）其中J为变换的Jacobi。由此知相互独立，服从标准正态分布。II产生随机变数令2024/7/1313正态分布（3）其中III根据统计理论，随机数的期望值为1/2，标准差为，随机变量随机变量是渐近正态分布的随机变量。当n足够大时便可用代替。在实际中，取即可取得满意的结果。特别，当时：2024/7/13147.2 Monte Carlo方法 Monte Carlo法积分法积分考虑两种：随机投点法和平均值法随机投点法假定是0，1上的连续函数,且，要计算积分即图中曲线下方的面积。向图示的单位正方形中均匀地投点，则该随机点落入曲线下方的概率为2024/7/1315随机投点法计算步骤STEP1产生两个随机数及，把作为随机点的可取坐标；STEP2检验随机点是否落入G内：若则记录落入G内的点增加一次。STEP3计算概率作为积分积似值2024/7/1316平均值法(1)投点法的误差：平均值法其误差估计以某个随机变量的简单子样的算术平均值作为所求积分I的近似值。2024/7/1317平均值法(2)由强大数定理知道，如果随机变量序列相互独立、同分布、期望值存在，那么当时，以概率1趋于积分值I。按照中心极限定理，只要随机变量序列相互独立、同分布、数学期望存在，有限标准差，那么当时，随机变量渐进地趋于标准正态分布N（0，1），即而在方法中，随机变量序列均满足上述两个定理条件。2024/7/1318平均值法(3)因此，上式表明：不等式成立的概率近似地等于。其中，当很小时，称为显著水平，而称为置信水平。如当时，可以有99.7%概率肯定落在区间内。2024/7/1319平均值法(4)MonteCarlo方法误差可以写为由此可以确定，对于给定的误差，N值应取为计算积分值的误差是在概率意义下的统计估值。模拟结果误差与标准成比，与模拟次数平方根成反比。要模拟结果的精度提高一位，就需要把增大100倍。2024/7/1320平均值法(5)单纯增大也不是一个有效办法。对于随机投点法来讲，由于积分的近似值渐近地服从正态分布，因此模拟结果误差为无法知道理论值，在实际计算中，只能用标准差的近似估计来代替，具体公式2024/7/1321平均值法(6)对于平均值法：渐近地服从正态分布，因此模拟结果误差为在实际中用：来代替。2024/7/13227.3减小方差的方法 l有许多种方法用于减小方差l重要性抽样l分层抽样等2024/7/1323重要抽样法重要抽样法假定要估计值：的值。罕见事件（Rareevent）的估计！在Matlab上算出的一个Y的结果为：均值：2.7514E-89,标准差为1.3526E-89,在5%的置信时为1.0E-880.2725,0.2788。重要性抽样法，是一种降低方差的抽样方法。其基本思想是以重要性抽样法，是一种降低方差的抽样方法。其基本思想是以i i个重要个重要性函数性函数g gi i(1)(1)代替原来的代替原来的i i个随机变量的概率密度函数，进行模拟抽样时，个随机变量的概率密度函数，进行模拟抽样时，改为从重要性概率密度函数中抽出。改为从重要性概率密度函数中抽出。2024/7/1324分层抽样法分层抽样法 把积分域分成若干个小区域，在每个小的积分域上按其重要性，选取不等的抽样数，进行局部的均匀抽样，代替在整个积分域上的均匀抽样。例：假定我们要估计，其中。令并且W=U为分层变量，因为：容易计算容易生成令，而选择m个等可能的分层，对所有的有。为了避免先导计算，置直接计算后的一个结果是：均值：0.787352；方差：0.04983892024/7/1325分层抽样法分层抽样法方差:分层抽样结果：转化为做估计的问题：计算10000次，分为100个区间，均值为0.7854，5%的置信区间：0.7853,0.7855此外，还有受控变量法等。在子区间上的方差会更小些，各采样N个2024/7/13267.4 拟Monte Carlo方法 另一类形式与MonteCarlo方法相似，但理论基础不同的“拟蒙特卡罗方法”（QuasiMonteCarlo方法）近年来也获得迅速发展。我国数学家华罗庚、王元提出的“华-王”方法即是其中的一例。这种方法的基本思想是：用确定性的超均匀分布序列（数学上称为LowDiscrepancySequences）代替MonteCarlo方法中的随机数序列。对某些问题该方法的实际速度一般可比MonteCarlo方法提高数百倍，并可大大提高计算精确度。由于上述Monte Carlo法给出的误差是概率性的，而需要给出一个界而非随机值。面积 2024/7/1327点集均匀性（UNIFORMITY）的测量 l 直观上，对于均匀分布于s-维单位超立方体 的s-维序列xn，及Is的子集J在体积相同的子集内应当分布相同数目的点。l 注意 总是成立。l 其中s(j)为J的（测度）体积。如果N个点是均匀分布的，则对所有J局部的Discrepancy应该很小。2024/7/1328对于不同的集合族对于不同的集合族，有两个特例有两个特例:l 定义定义：星号Discrepancy为 ，l其子集J*为形如 的Is的族定义定义:（极端,extreme）Discrepancy为，l其子集J为形如的Is的族。l性质性质：l（1）l（2）如果 满足 ，l则 2024/7/1329两个定理l定理：如果 ，则l定理：如果 ，则2024/7/1330用此描述的积分的界限：l定理（Koksma）：如果函数f有0，1上的有界的变分V（f），则对任意 有:l对N个点：于均匀分布于s-维单位超立方体 的s-维序列 xn，在体积相同的子集内应当分布相同数目的点 2024/7/1331以b为基的基础区间：其中，对于 有定义：令 为整数。一个以b为基的(t,m,s)-网是Is中bm个点的集合P，满足对每一以b为基的测度为 的基本集，当t=0时，每一E中只有一个点；当t=m时，只用一个E，即Is，全部点都有在E中；对于1维，E只能取到b-d以大中d只能取到m，此时每个基本区间中只有一个（t=0）点（基本区间最多）；而当d=m-1时，有d个基本区间，每个区间中有bm-1个点。当t=m时，只用到一个基本区间。2024/7/1332定义和定理（1）l定义：令 为整数，中的序列 是一个以b为基的(t,s)-序列，如果对所有的 ，满足 的所有xn构成的集合为以b为基的(t,m,s)-网。l定理：对一个基 的(t,m,s)-网P，其星号 Discrepancy满足 定 理：对 一 个 偶 数 基 b的(t,m,s)-网 P，其 星 号Discrepancy满足2024/7/1333l当s=2,3,4时，有更好的界：(1)(2)(3)定义和定理（2）2024/7/1334经典的构造：对于一维情形，较好确定星号Discrepancy ，由于 其中等式成立当 拟Monte Carlo法积分为 即古典积分中取中点的方法。对 ，定义关于b的模 ，每一个n有下面的唯一以b为基的展开 其中 。注意对足够大的j ，即和式实际上是有限的。2024/7/1335定义定义:对 ，关于b的基逆函数（radical-inverse function）其中 。定义：对 ，关于b的van der Corput序列为如果 是基b的van der Corput序列，则当 时，l van der Corput序列是构成超均匀分布序列的基础，目前，许多其它的序列均是对此进行变化后得到。l J H Halton（1960）定 理：选 择 s个 两 两 互 素 的 基 ，即当 时 ，则 是低Discrepancy序列（S），满足2024/7/1336广义的广义的van van derder CorputCorput序列序列：其中为 的一个置换。序列可以如下递归生成：会有一定改进。另一族序列是通过考虑无理数的因子得到：l对 令 为u的分数部分，注意 。对无理数z，令S（z）为序列 ，令 为z的连分数展开，其中部分商 ，并且 ，z的渐近值的分母记为 2024/7/1337定理定理 ：令z为无理数及 ，则N可以表示成为 ，其中 为唯一的满足 的非负整数，为非负整数，满足 当 时。同时，2024/7/1338一般的（t，s）序列的构造方法（Niederreiter，1987提出，S.Tezuka 1993稍作修改）（1）R 是基数为b的交换环，（2）对 ，是B到R上的双射（BIJECTION），并且对足够大的r有（3）对满足 及 的i，j，为R到B的双射，且 满足对所有的I和足够大的j（4）对如上所述i，j，r，为交换环R的元素。如果 是n 的b进制展开，记 其中 。序列 为一（t,s）序列。2024/7/1339超均匀分布与伪随机数比较超均匀分布与伪随机数比较2024/7/13407.5 在优化中的应用lMARKOV过程的仿真；l排队系统的仿真；l随机搜索2024/7/13412024/7/1342例：例：串匹配的随机算法（续）串匹配的随机算法（续）令p为集合1,2,nt2中随机选取的素数，其中t=m-n+1.(xi)p=ximodpX和Y(i)的手印值:（fingerprints）Bp(x)=(x12)p+x2)p2)p+x3)p2Bp(Y(i)=(yi2)p+yi+1)p2+yi+2)p2Bp(Y(i+1)=(Bp(Yi)-(2n-1)pyi)p)p2)p+yi+n)p=(Bp(Yi)-2n-1yi)2+Yi+n)p如果如果 X=Y(i)X=Y(i)，则有则有Bp(X)=Bp(Y(i)Bp(X)=Bp(Y(i)，但反过来不成立但反过来不成立。多次做此检测即可！2024/7/1343例：例：串匹配的随机算法串匹配的随机算法 （续）（续）例如：X=10110,Y=110110n=5,m=6,t=m-n+1=2假定p=3.Bp(X)=(22)3=1Bp(Y(1)=(27)3=0XY(1)Bp(Y(2)=(0-24)2+0)3=1X=Y(2)再选择其他的p进行检验。结论：如果从1,2,nt2中选出k个不同的素数，则当nt29时，全部通过检验后发生错误的概率小于。2024/7/1344例：例：串匹配的随机算法串匹配的随机算法 （续）（续）例：n=10,m=100,t=m-n+1=91nt=91029令k=4，则通过检验后的出错概率小于(0.0229)42.7510-72024/7/1345