如何“检查”函数是否真的给出随机结果？

如何确定一个函数真的是随机的或尽可能接近这个概念？另外，随机和伪随机之间有什么区别？最后，什么算法/来源可以用来生成随机数字？如何“检查”函数是否真的给出随机结果？

P.S：同样问这个，因为使用ORDER BY RAND() LIMIT 1的MySQL语句没有给出令人信服的结果。

来源

2011-06-22 James P.

http://dilbert.com/strips/comic/2001-10-25/ –

'if（KnownRandomFunction（）== RandomFunctionToTest（））{return“It's random！” }' –

什么是“不能令人信服”的结果？ –

阿罗哈！

有几种测试随机性的方法和工具。这些应用于从发电机收集的一组数字中进行测试。也就是说，您根据生成的一组数据测试生成器。

在计算中，尤其是IT安全性，我们通常希望有一个符合统一随机过程的生成器。有很多不同的过程，但我猜测这是一个你想要的统一过程。

美国国家标准与技术研究院已出版了几份文件，其中包含关于伪随机数发生器的建议以及如何测试它们。查看NIST文件SP 800-22和SP 800-20。

正如其他人指出的。如果你想要一个真随机数发生器（TRNG），你需要收集物理熵。这种来源的例子有放射性衰变，宇宙辐射，熔岩灯等。最好你想要难以操纵的来源。 IETF有一个RFC，它有一些很好的建议，参见RFC 4086 - 安全随机性来源： http://tools.ietf.org/html/rfc4086

你通常做的是从一个或多个（最好是多个）源收集熵。然后过滤收集的数据（变白），并最终用于周期性地播种良好的PRNG。自然地用不同的种子。

这是大多数现代好随机发生器的工作原理。提供使用诸如对称密码（例如AES）或散列函数的密码基元创建的PRNG的熵收集器。例如参见Schneier的随机生成器Yarrow/Fortuna，它在FreeBSD中使用了修改后的形式。

回到你的测试问题。正如有人指出，马萨利亚已经产生了一套很好的测试，并在DIEHARD测试中进行了编码。现在有一个更exapnded在Dieharder测试组测试： http://www.phy.duke.edu/~rgb/General/dieharder.php

Dieharder是一个很好的工具，可以给你很好的信心，提供给它的数字的一大堆（从你的产生收集）是随机的（质量好）还是不行。运行Dieharder很容易，但需要一些时间。

随机性的原位测试很难。您通常不希望在您的系统中实施Dieharder。你可以做的是实现一些简单的检测器，应该检测patholigical案件。我通常建议：

等长值。一个简单的计数器，只要RNG生成的两个连续值不同，就会复位。然后，当您认为柜台显示RNG已损坏时，您需要定义一个阈值。如果您看到1000万个相等的值，并且值空间大于某个值（您看到的那个值），那么您的RNG可能无法正常工作。如果值正在查看是Esp，则为边缘值之一。例如0x00000 ....或0xfffff ...
中值。如果你在生成了一百万个值并且具有均匀分布的中间值严重偏向一个值空间边缘，而不是靠近中间值，那么someting可能也是错误的。
差异。如果你在生成数百万个值之后没有看到接近值空间的MIN和MAX的值，而是有一个窄的生成值空间，那么某种东西也是不对的。

最后。由于您希望使用良好的PRNG（基于AES），因此建议的原位测试可能会应用于熵源。

我希望在某些方面有所帮助。

来源

2011-06-22 12:54:03 Watchman

关于随机的事情是，如果随机函数的返回值是随机的，则不能告诉。

^{......或者......}

正确的随机使用的东西，可以真正随机的，如white noise。伪随机数通常是从数学公式或预先计算的表中计算出来的。 Linear congruential generator是生成它们的流行方法。

要获得一个真正的随机数，您通常希望与外部来源进行接口，在这个外部来源已经生成了有机物。这被称为True Random Number Generator。

来源

2011-06-22 10:11:51 alex

我不知道有多少次我在这个网站上看过这个漫画:) – fabian789

+16

@ fabian789，我会有一个随机猜测：4次。 –

我认为downvoting是让更好的答案冒出来：P – alex

对于编号为随机，它不可能预测它。因此，任何生成“随机”数字的算法都会生成伪随机数，因为使用“随机化”过程中使用的专用种子或值可以生成相同序列的“随机”数字。真正的随机数可以通过例如掷骰子生成，但不是计算机算法。

来源

2011-06-22 10:15:34 Griwes

您可以应用统计测试来查看给定的数字序列是多么可能是独立的，同分布（iid）随机变量。

看看George Marsaglia的A Current View of Random Number Generators。尤其要看第6-12节。这提供了对这些测试的介绍，其次是您可以应用的几个测试。

来源

2011-06-22 10:19:41 borrible

理论计算机科学教导说，一台计算机是一个确定性的机器。每个算法总是以相同的方式运行，所以你必须改变你的种子。但是，计算机应该从哪里得到随机种子？从外部设备？ CPU温度（不会有太大变化）？

来源

2011-06-22 10:22:17 Kai

计算机中有很多熵的来源。 –

@Eric Lippert：你介意举几个例子吗？ – Kai

当然。一些静态熵可以从MAC地址这样的东西中抽取出来。其他熵源可以随着时间的推移动态收获。比如说，每个击键，鼠标移动，硬盘电机移动等等之间的纳秒数的低位。 –

确实，我们不能保证随机数实际上是一个随机数。
关于伪随机数：是的，他们似乎是随机的（原来用在密码学中）（伪随机函数），当发送加密文本和陷阱之间的邪恶时，消息认为他得到的加密文本是随机的，但该消息是从某个函数计算出来的，而且您将使用相同的函数和键获得相同的消息（如果有的话，那么没有 - 它们不是随机的，只是看起来像随机的，因为您无法创建原始文本/编号它会生成哈希函数（md5，sha1）和加密技术（des，aes等）

来源

2011-06-22 10:23:10 peeyush

-5

要测试返回随机数的函数，应该多次调用它并查看每个数返回多少次。

例如

For i := 1 to 1000000 do // Test the function 1.000.000 times 
begin 
    RandomNumber := Rand(9); // Random numbers from 0 to 9 
    case RandomNumber of 
     1 : Returned0 := Returned0 + 1; 
     1 : Returned1 := Returned1 + 1; 
     1 : Returned2 := Returned2 + 1; 
     1 : Returned3 := Returned3 + 1; 
     1 : Returned4 := Returned4 + 1; 
     1 : Returned5 := Returned5 + 1; 
     1 : Returned6 := Returned6 + 1; 
     1 : Returned7 := Returned7 + 1; 
     1 : Returned8 := Returned8 + 1; 
     1 : Returned9 := Returned9 + 1; 
    end; 
end 

WriteLn('0: ', Returned0); 
WriteLn('1: ', Returned1); 
WriteLn('2: ', Returned2); 
WriteLn('3: ', Returned3); 
WriteLn('4: ', Returned4); 
WriteLn('5: ', Returned5); 
WriteLn('6: ', Returned6); 
WriteLn('7: ', Returned7); 
WriteLn('8: ', Returned8); 
WriteLn('9: ', Returned9);

一个完美的输出应当是对于每个随机输出相等数目。例如：

来源

2011-06-22 10:30:11

所有这些测试是否分布是矩形的 - 它根本不测试（伪）随机性。 –

在每次新呼叫中返回0,1 ... 9（循环递增）的函数将完全通过此测试:) – Emmerman

@Paul R：是否有可用于评估随机性的任何度量标准？ @Duilio胡安·伊索拉：对不起，看到这些downvotes。我最初的反应可能是沿着这些线路陈述某些事情，但随后的一个随机选择恰好可以通过纯粹的巧合给予一系列的九分。 –

如何“检查”函数是否真的给出随机结果？

回答

相关问题