 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
第四章 随机数发生器和随机变量的产生
下载积分：900
内容提示：第四章 随机数发生器和随机变量的产生
文档格式：PPT|
浏览次数：10|
上传日期： 06:01:38|
文档星级：
该用户还上传了这些文档
第四章 随机数发生器和随机变量的产生
官方公共微信一.在j2se里我们可以使用Math.random()方法来产生一个随机数，这个产生的随机数是0-1之间的一个double，我们可以把他乘以一定的数，比如说乘以100，他就是个100以内的随机，这个在j2me中没有。&二.在java.util这个包里面提供了一个Random的类，我们可以新建一个Random的对象来产生随机数，他可以产生随机整数、随机float、随机double，随机long，这个也是我们在j2me的程序里经常用的一个取随机数的方法。&三.在我们的System类中有一个currentTimeMillis()方法，这个方法返回一个从号0点0分0秒到目前的一个毫秒数，返回类型是long，我们可以拿他作为一个随机数，我们可以拿他对一些数取模，就可以把他限制在一个范围之内啦&其实在Random的默认构造方法里也是使用上面第三种方法进行随机数的产生的&对于方法二中的Random类有以下说明：&java.util.Random类有两种方式构建方式：带种子和不带种子&不带种子：&此种方式将会返回随机的数字，每次运行结果不一样&public&class&RandomTest&{&public&static&void&main(String[]&args)&{&&&java.util.Random&r=new&java.util.Random();&for(int&i=0;i&10;i++){&&&&&System.out.println(r.nextInt());&}&}&带种子：&此种方式，无论程序运行多少次，返回结果都是一样的&public&static&void&main(String[]&args)&{&&&java.util.Random&r=new&java.util.Random(10);&&&for(int&i=0;i&10;i++){&&&&&System.out.println(r.nextInt());&&&}&}&两种方式的差别在于&(1)&首先请打开Java&Doc，我们会看到Random类的说明：&此类的实例用于生成伪随机数流，此类使用&48&位的种子，该种子可以使用线性同余公式对其进行修改（请参阅&Donald&Knuth&的《The&Art&of&Computer&Programming,&Volume&2》，第&3.2.1&节）。&&如果用相同的种子创建两个&Random&实例，则对每个实例进行相同的方法调用序列，它们将生成并返回相同的数字序列。为了保证实现这种特性，我们为类Random指定了特定的算法。为了&Java&代码的完全可移植性，Java&实现必须让类&Random&使用此处所示的所有算法。但是允许&Random&类的子类使用其他算法，只要其符合所有方法的常规协定即可。&&Java&Doc对Random类已经解释得非常明白，我们的测试也验证了这一点。&(2)&如果没有提供种子数，Random实例的种子数将是当前时间的毫秒数，可以通过System.currentTimeMillis()来获得当前时间的毫秒数。打开JDK的源代码，我们可以非常明确地看到这一点。&/**&&*&Creates&a&new&random&number&generator.&Its&seed&is&initialized&to&&*&a&value&based&on&the&current&time:&*&Random()&{&this(System.currentTimeMillis());&}java.lang.System#currentTimeMillis()&*/&public&Random()&{&this(System.currentTimeMillis());&}&另外：&&random对象的nextInt(),nextInt(int&n)方法的说明：&int&nextInt()&&&&&&返回下一个伪随机数，它是此随机数生成器的序列中均匀分布的&int&值。&&int&nextInt(int&n)&&&&&&返回一个伪随机数，它是从此随机数生成器的序列中取出的、在&0（包括）和指定值（不包括）之间均匀分布的&int值。
阅读(...) 评论()如何评价一个伪随机数生成算法的优劣？
【余天升的回答(133票)】:
一个比较简单的方法，用数填充一个位图，下面是一个填充黑白图像的例子。
这个是用C#的System.Random类生成的随机数填充的位图
这个是用php的rand函数生成的随机数填充的位图
哪个比较差一目了然。
【知乎用户的回答(77票)】:
给出了一个直观的答案，不过这只是一个非常特殊的特例，实际上绝大多数随机数发生器用这种方法根本看不出来质量。
正确的方法应该是参考德国联邦信息安全办公室给出了随机数发生器质量评判的四个标准。PDF链接在这里
里面列出了四个判别随机数序列质量的准则
K1 — A sequence of random numbers with a low probability of containing identical consecutive elements.K2 — A sequence of numbers which is indistinguishable from 'true random' numbers according to specified statistical tests.K3 — It should be impossible for any attacker (for all practical purposes) to calculate, or otherwise guess, from any given sub-sequence, any previous or future values in the sequence, nor any inner state of the generator.K4 — It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.大致翻译：
K1——相同序列的概率非常低
K2——符合统计学的平均性，比如所有数字出现概率应该相同，卡方检验应该能通过，超长游程长度概略应该非常小，自相关应该只有一个尖峰，任何长度的同一数字之后别的数字出现概率应该仍然是相等的等等K3——不应该能够从一段序列猜测出随机数发生器的工作状态或者下一个随机数K4——不应该从随机数发生器的状态能猜测出随机数发生器以前的工作状态我们一般用的随机数发生器至少要符合K1和K2，而用于加密等应用的随机数发生器应该符合K3和K4。
的例子里，应该是PHP的随机数发生器不满足K2。这是一个非常巧的例子，只是PHP 5在Windows底下调用rand()函数的时候会有这样的情况，别的组合不会产生这么巧的图像。实际上PHP提供了一个质量高的多，非常好的随机数发生器mt_rand()，在涉及网页安全的时候请选用这个函数。关于mt_rand()的原理，可以参考这个关于梅森旋转的Wiki网站： /
（英文）。
【李楠的回答(5票)】:
有一系列的测试可以判断一个随机数生成器的优劣。NIST发布了一个工具包专门用来做这件事情。
网页为英文，而且我不知道是否需要翻墙。
【杨勤荣的回答(2票)】:
据我所知，卡方检测是一个比较有效的方法；还有一个方法就是以该随机数发生器为基础，用蒙特卡洛方法求高维数值积分（例如n维球的体积和面积），如果随机数生成器足够好，积分结果应该能很好地逼近理论值。
【王洪城的回答(4票)】:
谈到随机性，这大概是一个令人困惑哲学问题吧。随机行为精确地说究竟指的是什么，最好是有定量的定义。Kolmogorov曾提出一种判定随机性的方法：对于无穷的随机数序列，无法用其子序列描述。J.N.Franklin则认为：如果一个序列具有从一个一致同分布的随机变量中独立抽样获得的每个无限序列都有的性质，则是随机的。这些定义都不是很精确，有时甚至会导致矛盾。可见数学家在谈到这个问题时是多么的审慎。
随机数生成器只是一种产生符合特定分布的随机数的算法。这些所谓的随机数序列实际上是周期性的。从实用的角度出发，随机数生成器如果能够在尽可能多的场合中产生正确的结果，那么它就是好的。但是这个愿望无法完全实现。因为每一个生成器都会在特定的场合失效，比如说可能无法达到随机数的均匀性或者随机数之间隐藏着关联。
已经有大量的随机数生成器，但是找到好的、易移植的、达到工业水准的随机数生成器是一个难以实现的目标。生成非均匀分布的标准方法是先产生均匀分布随机数，然后将其转化为特定分布的随机数。我在博客中有简易介绍。Knuth曾经说
. . . look at the subroutine library of each computer installation in your organization, and replace the random number generators by good ones. Try to avoid being too shocked at what you find.
@余天升的答案测试的大概是随机数分布的随机性和周期性，即随机数的出现无规律，周期要足够长（这是我猜的，猜错了表打我）。这当然是一个很好的方法，图也很简单直白。但是也有其他一些因素需要考虑。对于不同的应用，这些因素的重要程度并不一样。比如说用物理方法产生的真随机数比由数学方法产生的伪随机数随机性更强，更难破解，但这并不能说明物理方法产生的随机数质量更高。假设我们并能够事先知道应用的场景，应该如何评价一个生成器的质量呢？我们并不知道采样的过程、样本的大小或者仿真中的维度。以下两点是很重要的：
生成器只提供预测，不提供保证。这是因为我们产生的只是有限数量的随机数，并且转换成特定分布的方法并不是足够好。因此，在特定的场合即使可靠的生成器也会失效。尽管没有保证，但是有数学上的安全性测度。这意味着我们可以从理论上知道周期长度、一些结构性质以及关联性等。周期长度会限制样本的大小；结构信息可以是我们确定在仿真中是否存在副作用；关联性质则对随机模拟而言很重要。
不言而喻，随机数生成的方法应是快速的，占用内存少的，实现简单，可移植，可并发执行，对于不同的参数都应当具有均匀的速度。更加重要的检测内容是对其统计性质的检测。统计检验又分为两类：一类是理论检验，另一类是经验检验。
先来说说理论检验。顾名思义，理论检验是先验的检验，能够预先告诉我们这些检验的结果将会是如何。如前所述，理论检验主要是检验随机数的周期，内在结构和关联性。发展这一类型的理论十分困难，至今的得到的结果一般是对整个周期的统计检验。对于线性同余算法得到的随机数，周期长度的平方根是一个比较好的样本大小的上限。因此对于一个好的生成器，必须能够使得对于某些参数能够得到最大的周期长度，并且能够计算出这样的参数。比如对于线性同余算法而言，最好的乘数是
.这个观点在很多书籍和论文中都有推荐，但是随着计算机计算能力的提高，这个观点已经不合时宜啦。因为对于现代的计算机而言，这样的周期还是太短了，现在而言m不应小于
.生成器的内部结构如栅栏结构和超平面点的分布也很重要。对于不同的生成器有特定的检测方法。结构检测用到最多的就是谱检验，谱检验就是基于相邻平行超平面之间最大距离的检验，该距离越大，生成器越差。如下图所示：
上图中随机数主要保持在平面内。
对于二维的情况如下图所示：
图中我们可以用少量的平行线来全部覆盖它们，由许多不同的平行线族，它们将会碰上所有的点。平行覆盖线的数目是一个重要的指标。图中我们可以用少量的平行线来全部覆盖它们，由许多不同的平行线族，它们将会碰上所有的点。平行覆盖线的数目是一个重要的指标。
将随机数生成器应用在并行进程中尤其要注意的是随机数之间是否关联，即独立性检测。比如用线性同余算法得到的均匀分布经Box-Muller转换成正态分布得到的点
落在一条螺旋线上，如下图：
从理论上可以证明所有的线性和非线性同余序列都存在长周期相关现象。如果几个并行处理器分别使用同一个同余序列的不同段落，分割时就应该避开具有强相关的分点。以上的3副图给人一种触目惊心的感觉，没想到我们平常用到最多的线性同余算法产生的随机数是如此的”不随机“，我想这种震撼类似于第一次用显微镜观察微生物发现一个不可思议的微观世界。的确，这类似于我们用超高分倍率的显微镜来观察我们得到的随机数，只有对于很精确的应用情境这种观察才是有价值的，否则只是杞人忧天、庸人自扰了。在这种情况下，简单的线性同余序列肯定是不适用的，应当使用具有更大周期的生成序列，尽管实际上只要生成这个周期中的很小的一部分。
理论检验是不够的，我们还需要经验检验。经验检验性对较简单，且有很多的方法。比如：
等分布检验：又称均匀性检验，将
【0,1[】区间分成k个相等的子区间，落在每个子区间的伪随机数个数应该相等。常用的是
检验。序列检验：相继的数偶独立一致分布。计算的是数偶对的出现次数。间隔检验：用来考察在某个范围内序列的出现的间隔长度。扑克检验：考虑5个相继整数组成的n个组，观察其出现模式。........
经验检验还有很多，不一一赘述了。
当然即使通过了所有的统计测试，这也不能证明什么，但是这提高了我们使用这个生成器的信心。
对于实际应用中，应该对不同的应用场景选择合适的生成器。当然也有一些通用的测量方法来告诉我们该生成器是否有可能是一个好的生成器。对于并行应用来说，很多通常情况下很好的生成器都不合适。我们可以为k个进程选择k个生成器，虽然这也不是一个很好的方法。通用的方法如下：
有一个比喻：随机数生成器就像抗生素，每一种都有副作用，没有安全的随机数生成器。好的随机数生成器应该是有理论检验的支持，充分的经验证据和良好的实际表现。遵循以下一些建议对于合理使用随机数生成器很有帮助：
不要相信只由一个生成器得到的随机数序列，在使用前用不同的生成器检验它们的结果。不要在没有理论依据和经验支持的情况下将几种生成器结合起来或并行。在使用前了解生成器的特性。
【知乎用户的回答(2票)】:
nist随机性测试方法频数测试：测试二进制序列中，“0”和“1” 数目是否近似相等。如果是，则序列是随机的。块内频数测试：目的是确定在待测序列中，所有非重叠的 长度为M位的块内的“0”和“1”的数目是否表现为随机分布。如果是，则序列是随机的。游程测试：目的是确定待测序列中，各种特定长度的 “0”和“1”的游程数目是否如真随机序列期望的那样。如果是，则序列是随机的。块内最长连续“1”测试：目的是确定待测序列中， 最长连“1”串的长度是否与真随机序列中最长连“1”串的 长度近似一致。如果是，则序列是随机的。矩阵秩的测试：目的是检测待测序列中，固定长度子序列的线性相关性。如果线性相关性较小，则序列是随机的。离散傅里叶变换测试：目的是通过检测待测序列的周期性质，并与真随机序列周期性质相比较，通过它们之间的偏离程度来确定待测序列随机性。如果偏离程度较小，序列是随机的。非重叠模板匹配测试：目的是检测待测序列中，子序列是否与太多的非周期模板相匹配。太多就意味着待测序列是非随机的。重叠模板匹配测试：目的是统计待测序列中，特定长度的连续“1”的数目，是否与真随机序列的情况偏离太大。太大是非随机的。通用统计测试：目的是检测待测序列是否能在信息不丢失的情况下被明显压缩。一个不可被明显压缩的序列是随机的。压缩测试：目的是确定待测序列能被压缩的程度，如果能被显著压缩，说明不是随机序列。线性复杂度测试：目的是确定待测序列是否足够复杂，如果是，则序列是随机的。连续性测试：目的是确定待测序列所有可能的m位比特的组合子串出现的次数是否与真随机序列中的情况近似相同，如果是，则序列是随机的。近似熵测试：目的是通过比较m位比特串与m-1位比特串在待测序列中出现的频度，再与正态分布的序列中的情况相对比，从而确定随机性。部分和测试：目的确定待测序列中的部分和是否太大或太小。太大或太小都是非随机的。随机游走测试：目的是确定在一个随机游程中，某个特定状态出现的次数是否远远超过真随机序列中的情况。如果是，则序列是非随机的。随机游走变量测试：目的是检测待测序列中，某一特定状态在一个游机游程中出现次数与真随机序列的偏离程度。如果偏离程度较大，则序列是非随机的。参考
测试程序前面有人给过了，这里重复一下地址
类似的测试标准和程序还有diehard
这个项目里面有开源的ENT测试。主要测试有五项。详细信息见链接
【金山的回答(0票)】:
请阅读NIST SP800-22文档，共15个测试项。NIST还提供对应的测试套件。采集完随机数，用渣电脑单线程测试的话，要好几个小时。
&&&&&本文固定链接:
【上一篇】
【下一篇】
您可能还会对这些文章感兴趣！
最新日志热评日志随机日志