[数学]蒙特卡罗方法概述(2) - 随机数

well

1．随机数的定义及产生方法
    我还真不知道什么叫随机，可能指表面的偶然性吧。数学上的定义是这样的：在连续型随机变量的分布中，最简单而且最基本的分布是单位均匀分布。由该分布抽取的简单子样称为随机数序列，其中每一个体称为随机数。单位均匀分布即［0，1］上的均匀分布。
    由随机数序列的定义可知，ξ1，ξ2，…是相互独立且具有相同单位均匀分布的随机数序列。也就是说，独立性、均匀性是随机数必备的两个特点。

产生方法:
1).随机数表。好像是计算机出现早期用的最多的方法。顾名思义，是事先做好一张包含随机数的表，使用的时候通过查表就可以得到随机数。随机数表是由0，1，…，9十个数字组成，每个数字以0.1的等概率出现，数字之间相互独立。这些数字序列叫作随机数字序列。如果要得到n位有效数字的随机数，只需将表中每n个相邻的随机数字合并在一起，且在最高位的前边加上小数点即可。例如，某随机数表的第一行数字为7634258910…，要想得到三位有效数字的随机数依次为0.763，0.425，0.891。
     因为随机数表需在计算机中占有很大内存，而且也难以满足蒙特卡罗方法对随机数需要量非常大的要求，因此，该方法不适于在计算机上使用。

2）．物理方法. 用物理方法产生随机数的基本原理是：利用某些物理现象，在计算机上增加些特殊设备，可以在计算机上直接产生随机数。这些特殊设备称为随机数发生器。用来作为随机数发生器的物理源主要有两种：一种是根据放射性物质的放射性，另一种是利用计算机的固有噪声。用物理方法产生的随机数序列无法重复实现，不能进行程序复算，给验证结果带来很大困难。而且，需要增加随机数发生器和电路联系等附加设备，费用昂贵。因此，该方法也不适合在计算机上使用。

3).最后一种方法就是通过算法在计算机上产生伪随机数，我们在下节里面讨论。


2．伪随机数
   在计算机上产生随机数最实用、最常见的方法是数学方法，即用如下递推公式：
            ξ(n+k)= Tξ(n), ξ(n+1),…, ξ(n+k-1))       n= 1, 2, …
产生随机数序列
    对于给定的初始值ξ1,ξ2…，ξk，确定ξn+k，ｎ=1，2，…。经常使用的是k=1的情况，其递推公式为：
                       ξ(n+k)=T(ξ(n))
对于给定的初始值ξ1，确定ξn+1，ｎ=１,２…

    用数学方法产生的随机数，存在两个问题：
a) 递推公式和初始值ξ1,ξ2…，ξk确定后，整个随机数序列便被唯一确定。不满足随机数相互独立的要求。
b) 由于随机数序列是由递推公式确定的，而在计算机上所能表示的[0，1]上的数又是有限的，因此，这种方法产生的随机数序列就不可能不出现无限重复。一旦出现这样的n＇，n″ (n＇< n″ )，使得下面等式成立：
                      ξ(n’+ i) = ξ(n”+ i)
随机数序列便出现了周期性的循环现象。对于k=1的情况，只要有一个随机数重复，其后面的随机数全部重复，这与随机数的要求是不相符的。
由于这两个问题的存在，常称用数学方法产生的随机数为伪随机数。对于以上存在的两个问题，作如下具体分析。
    关于第一个问题，不能从本质上加以改变，但只要递推公式选得比较好，随机数间的相互独立性是可以近似满足的。至于第二个问题，则不是本质的。因为用蒙特卡罗方法解任何具体问题时，所使用的随机数的个数总是有限的，只要所用随机数的个数不超过伪随机数序列出现循环现象时的长度就可以了。
    用数学方法产生的伪随机数容易在计算机上得到，可以进行复算，而且不受计算机型号的限制。因此，这种方法虽然存在着一些问题，但仍然被广泛地在计算机上使用，是在计算机上产生伪随机数的主要方法。

产生方法很多，我这里介绍几个常见的产生方法：
a) 乘同余方法。乘同余方法是由Lehmer在1951年提出来的，它的一般形式是：对于任一初始值x1，伪随机数序列由下面递推公式确定：
                  x(i+1) = a * x(i) (MOD M)
                  ξ(i+1) = x(i+1) / M
a 为一常数

为了便于在计算机上使用，通常取 ：                                        Ｍ=2^s
            其中s为计算机中二进制数的最大可能有效位数
                                x1= 奇数
                                a = 5^(2k+1)
            其中k为使5^(2k+1)在计算机上所能容纳的最大整数，即a为计算机上所能容纳的5的最大奇次幂。一般地，s=32时，a=5^13；s=48，a=5^15等。伪随机数序列的最大容量λ(M)=2^(s-2) 。
    乘同余方法是使用的最多、最广的方法，在计算机上被广泛地使用。

b)乘加同余方法
产生伪随机数的乘加同余方法是由Rotenberg于1960年提出来的，由于这个方法有很多优点，已成为仅次于乘同余方法产生伪随机数的另一主要方法。
    乘加同余方法的一般形式是，对任意初始值x1，伪随机数序列由下面递推公式确定：
x(i+1) = (a * x(i) + c) (MOD M)
                  ξ(i+1) = x(i+1) / M
a,c 为一常数

其中实际用得多的是素数模乘同余发生器（PMMLCG）,反馈位移寄存器法(FSR),以及组合发生器等。大家可以参考北大出的《统计计算》。

3．对伪随机数的统计检验
    判断伪随机数序列是否满足均匀和相互独立的要求，要靠统计检验的方法实现。对于伪随机数的统计检验，一般包括两大类：均匀性检验和独立性检验
由于公式原因，就不详细说了，将来可能会补上吧

OK.我们到目前为止，已经完成了 Monte Carlo 方法的基础。下面会进一步讨论并给出几个应用。期望我的身体别。。。坚持写完就好了 ：）

cyfdecyf

Linux 内核似乎是可以记录键盘的敲击速度，硬盘的某些动作然后将它们放入随机数池，对应的设备应该是 /dev/hw_random 吧（不过从 cat 出来的东西看很奇怪，不随机），这个是不是也可以算是物理随机数呢？

伪随机数的产生没怎么看懂，数学烂啊……

祝你身体健康！（我也要注意自己的身体了）

well

谢谢你的祝福！
/dev/hw_random没研究过，不过听你的描述似乎算是物理随机，曾经在phrack杂志上看到过利用mouse的随机运动来产生随机数的文章，可能同出一辙

伪随机数的产生不用看那个原理，直接看具体产生方法你就会有感觉了，x(n+1)这里(n+1)是下标，x(n+1)=(a*x(n)+c)(MOD M)是线性随机数产生的通式，就是用前一项乘以一个数再加上一个数后对M取模就得到了下一项，是一种递推的方法。

xiaokang

随机地选择的数

最早期人们获的随机数的方法是通过摇筛子，分牌等等方法获的

1927，Tippett 从人口统计调查报告中随机的取的了一张超过40000个随机数字的表，后来人们造出了一些机械装置，用来生成随机数

1939，Kendall和Babington-Smith使用了第一部那样的机器造出了100000个随机数字表

1951，Feranti Mark  I 计算机的内置指令，使用了一个电阻噪声器将20个随机位放进了累加器

1955，RAND公司发步了一张有100万个随机数字的表被广泛的使用

编制维护这样的表，在当时由于内存空间和输入时间的要求，这种方法在计算机程序中实用性有限，不能精确的重复以前的计算

随机数表的复兴在90年代，1995年，George Marsalia将一个噪声二极管的电流输出和经过扰频的rap音乐叠加在一起生成了650M的随机值并且做成了演示光盘，也就是我们所说的“黑白噪声。

伪随机序列或被称为拟随机序列，来源于1946年，Neumann建以取前面的随机数的平方，并抽取中部的数字这种技术，但后来国外的牛人们证明了这种方法不是最好的，危险在于这个序列容易产生重复元素的短循环，要是0作为这个序列的一个数，它将不断重现本身，

随机数并不是通过随机地选择的方法就可生成的，应该使用某些理论！！！！！！！！1

祝楼主身体健康，祝学习快乐~~~~~~~~

unisun1981

linux是可以选择把设备产生中断的时间放入内核随机数池吧？
另外，可不可以介绍一下随机理论在计算机中的应用吗？ 呵呵，我是半路出家，对操作系统比较感兴趣

xiaofeng_jia

期待实例详解!!

wide288

是啊。很希望早日看到随机数或者其它此类方面的应用举例。

兄弟们要:sleep 好啊。

LiEn

不错，很有启发性。