随机数及简明概率论（讲稿）

5.随机数及简明概率论真、伪随机数产生方法：(1)取中法，(2)线性同余产生器，(3)反馈位移寄存器C/C++RandomgeneratorCERNRoot三种Randomgenerator随机性的检验：均匀性，独立性简明概率论平均值，方差中心极限定理常见分布函数：Gauss,Landau,Chi2分布置信度随机性的检验：correlationfunction抽样直接抽样，变换抽样，取舍取样加、减、乘抽样

5. 随机数及简明概率论 真、伪随机数 产生方法：(1) 取中法, (2) 线性同余产生器, (3) 反馈位移寄存器 C/C++ Random generator CERN Root三种Random generator 随机性的检验: 均匀性，独立性 简明概率论 平均值，方差 中心极限定理 常见分布函数: Gauss, Landau, Chi2分布 置信度 随机性的检验: correlation function 抽样 直接抽样, 变换抽样 ，取舍取样 加、减、乘抽样

试验者时间投娜次数相交次数引言：布冯实验园周车估计值Wolf25321850年50003.1596Smith1855年32041218.53.1554as1860年600382.5C.De Morgan3.137Fox1884年10304893.15951808Lazzerini1901年34083.141592911859Reina1925年25203.1795f(h,α) dhdα该试验方案是：在平滑桌面上划一组相距为s的平行线，向此桌面随意投郑长度1<s的细针，从针与平行线相交的概率就可以得到元的数值设针与平行线的垂直方向的夹角为α，细针与平行线相交的概率为投影长度与平行线间距之比，即cosαl=|cosαl，又由于|cosαl的平均值为2卫Icos alda =元元10假如在N次投针中，有M次和平行线相交。当N充分大时，相交的频数M/N就近似为细针与平行线相交的概率。既有2N元~M

引言: 布冯实验 𝑙 ≤ 𝑠 𝑓(ℎ, 𝛼 dℎd𝛼

随机数随机数可分为两种类型：真随机数和伪随机数●（一)真随机数真随机数数列是在某次产生过程中是按照实验过程中表现的分布概率随机产生的，其结果是不可预测的，是不可见的。因而也不可能重复产生两个相同的真随机数数列?真随机数的产生方法：。（1）物理方法：放射性物质放出的粒子数，电子设备的热噪音，宇宙射线的触发时间，优点是产生的随机数的具有好的独立性和均匀性，缺点是技术含量要求高，需要配备专门的物质和仪器，费用昂贵。（2)人工方法：比如掷般子，抛硬币，抽签，摇号等。优点是简单易行，缺点是如果需要大量的随机数的情况，执行效率非常低，而且无法重复实现，给验证结果带来很大困难在密码学等关键性应用中，人们一般使用真随机数●计算机程序不能产生绝对的真随机数

随机数

伪随机数。“伪”随机数的概念解释计算机产生的都是”伪随机数“。真随机数是一种理想的随机数，即使计算机怎样发展，它也不会产生一串真机数。计算机只能生成相对随机的随机数，即伪随机数。伪随机数并不是假随机数，这里的“伪”是有规律的意思，就是计算机产生的伪随机数既有真随机数的随机性质。又有伪随机数独有的规律性质。这种规律性质是指计算机产生的伪随机数列是一个确定性数列，它是按照一定的算法通过数学递推公式模拟产生的，其结果是确定的，是可见的。可以这样认为这个可预见的结果其出现的概率是100%。。但是如果确定性的计算方法经过精心设计，其依赖的信息足够大，足够复杂，使人力其至是机器都难以猜出其中的规律（科学地讲是随机序列能够通过独立性，均匀性等一系列的统计检验，我们就说输出的数是随机数序列与真正的随机数具有相近的性质

伪随机数

伪随机数的产生比如电脑可以记录鼠标点击次数、鼠标移动范围、键盘操作次数，系统使用时间（确精到毫秒以下）、当前时间（确精到毫秒以下）等不确定因素来做随机因子，这样出来的伪随机数也可作为真随机数来使用。。产生伪随机数的算法被称为伪随机数产生器。理论上，我们要求伪随机数产生器具备以下特征：。（1)良好的统计分布特性，这是最重要的一点：（2）高效率的伪随机数产生：·（3）伪随机数产生的循环周期长，至少大于随机数使用的个数。（4）伪随机数可以重复产生：然而实际使用的伪随机数产生程序还没有一个是十全十美的，因此我们要求产生的伪随机数应当能通过尽可能多的统计检验，以便人们放心使用

伪随机数的产生

取中法虽然0.1区间上的均匀分布十分简单，但是这个简单分布的随机数对使用随机模拟方法解决问题是十分重要的。许多其他形式的分布（如正态分布，指数分布，二项分布等的随机数通过舍选变换等抽样方法，都可以从0.11区间的均匀分布的随机数，经过变换得到。最早的伪随机数产生器可能是冯诺依曼平方取中法：该方法首先给出一个2r位的数，取它的中间的r位数码作为第一个伪随机数：然后将第一个伪随机数平方构成一个新的2r位数，再取中间的r位数作为第二个伪随机数。如此循环便得到一个伪随机数序列。比如一个十进制数列的例子。Xo三6031，递推之后x1=3729，,X2=9054,X3=9749相应的[0,1]上的均匀分布就为s；=1000(注：以后如不做特殊说明,一般，1,Sn...表示01]区间的上均匀分布的抽样序列)这种方法虽然简单，但是均匀性不好，且数列很快趋近于0，数列的长?度也难以确定

取中法

线性同余法●如今比较流行，并用得最多的是线性同余产生器，全称为LinearCongruenceGenerator，此方法利用数论中的同余运算来产生随机数，故称为同余发生器。有关同余运算的的相关性质请自行参考数学相关书籍。●通过如下的线性同余关系递推公式式来产生数列rn+1= (arn +c)(modm)。那么[0.1]区间上的均匀分布的随机数为Sn=an/m。显然nE[0,1],上式中参数a,c,m.xo的选取十分关键。其中xo称为种子，改变它的值就得到基本序列的不同区段。a，c,m，o为大于零的整数，分别叫做乘子，增量，模和初值。选择这些参数时需要使得产生出的伪随机数的循环周期要尽可能长

线性同余法

线性同余法xn+1 =(6x, +7)(mod 5), x。 = 24, 1, 3, 0, 2, 4, 1, 3, ...xn+ =(27x, +11)(mod 54), x =211, 38,11,

线性同余法 4, 1, 3, 0, 2, 4, 1, 3, . 11, 38, 11,

线性同余法an+1=(acn+c)(modm当c≠0时可以实现最大周期m（注：这里只给出结论，数学证明不需要作深入了解，相关证明可参考相关同余的性质）同时要达到最大周期m.还需要同时满足以下条件：。（1）c与m互质（即它们的公因数只有1）。(2)对m的任一因子p,满足a三1(modp),即a-1应被p整除（3）如果4是m的因子，则a三1（mod4），即a-1应被4整除实际应用中，通常选取：m=2L,a=4g+1c=2p+1●其中p,9,L均为正整数，此时：trTn+1=[(4g+1)rn +(2p+1)(mod2'), Sn=上述参数的一般是通过定性分析和计算机试验来选择，使得到的伪随机数列具有足够长的周期，而且独立性和均匀性都能通过一系列的检验

线性同余法

C++的线性同余法函数来初如果想每次产生的随机数不同，通常我们需要srand始化随机数发生器，即为随机数发生器设定种子：void srand(unsigned seed);此函数同样来自于stdlib.h。至于种子怎么选，一般常用的方法是利用time函数（声明在头文件time.h）来获得系统时间，然后将time_t型数据转化为unsigned型再传给srand函数，即srand((unsigned) time(NULL );如果想产生其他范围的随机数，例如a，b则需要利用求余运算rand%(b - a) + a;如果是产生0.11范围内的浮点型随机数，则(double)randO/RAND_MAX

C++的线性同余法