logo标签列表

如何测试随机生成器

testingrandom
43

我需要测试一个随机数生成器，该生成器可以随机产生数字。如何确保所生成的数字是随机的。

12
在 Stack Overflow 上，我们已经被那个漫画攻击了很多次，现在我甚至能够认出221而不必跟随链接 :) - paxdiablo
1
我只是认识xkcd.com这个域名，这在我的经验中更加稳妥。 - Coxy
11
更好了：http://www.random.org/analysis/dilbert.jpg - Stefano Borini
对于字符串生成器，我建议将结果添加到列表中并检查其是否存在。但对于数字，您应该依靠统计数据。 - gsscoder
这是我如何在C#中测试随机字符串生成器的方法：https://github.com/gsscoder/CSharpx/blob/master/tests/CSharpx.Specs/Outcomes/StringUtilSpecs.cs#L30。 - gsscoder
12个回答
18
15
使用卡方检验。你使用哪种编程语言？我可以提供一个C++的例子。
基本上：
- 在"桶"中放置随机数（多次）。 - "桶"数减1等于自由度。 - 将"桶"计数与"预期"计数进行比较，得出卡方结果。 - 使用卡方计算器查看获得这些结果的概率。
3
请确保桶内的内容是随机填充的，而非按顺序填充。 - cjk
1
是的，这就是事情变得更加困难的地方。 - Jon Reid
3
这是循环证明。如果我想确定随机位是否足够随机，我如何从尚未测量的随机性中获取任何随机性来随机采样位？ - Ursa Major
1
是的，我不知道如何验证桶是否随机填充。我所能做的就是在我的答案中描述的内容（这已经足够好了）。 - Jon Reid
11

这里是如何开始的详细说明。任何随机数生成器的初步测试都是由NIST使用的单比特测试，它仅计算1和0的数量。http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html

关于测试随机数生成器的注意事项： 我们实际上不需要太多的RNG测试，因为许多测试“包含”彼此。

尽管如此，这里描述了一种简单而有效的新的有序频率测试，适用于位。该测试包含了任何期望50-50的频率测试，因为它更为严格。

定义：t=扔 / 试验 b=箱子 / 球 s=一组扔 n=一组组扔

由于硬币投掷通常不是50-50的，因此可以利用4000万个位的池以极大的效果进行这个新测试。

当硬币被投掷100次时，期望值为53.9795和46.0205，有时会出现更多的正面或反面。50-50不是有序箱子的期望值，所以这个测试比任何期望50-50的频率测试都要好。
步骤1：样本大小的选择:100次/位。
步骤2：场次数的选择:50场永远不够，即使样本量在百万级别。400通常足够了。2000收敛得很好，因此使用了2000个不同的100次投掷样本。超过2000没有太多增益。

2000次100次抛硬币的期望值: 50-50 159.1784748 (注意，50-50仅发生了7.96%的时间。) 51-49 312.1146564 52-48 294.1080416 53-47 266.362 54-46 231.8335926 55-45 193.8971865 56-44 155.8102392 57-43 120.2745706 58-42 89.16907819 59-41 63.47629295 60-40 43.37546685 61-39 28.4429291 62-38 17.89152 63-37 10.79171042 64-36 6.238957586 65-35 3.455422663
66-34 1.832421109 67或更多 1.747439674

对于bin b=2和tosses t=100，得到确切百分比的方程为： 对于100-0，赔率为1 / (2^99) = 1 / (2^(t-1)) 然后，从这里开始构建， 对于99-1，之前乘以100（t）再除以1 对于98-2，之前乘以99（t-1）再除以2 对于97-3，之前乘以98（t-2）再除以3 ...跳过... 对于51-49，之前乘以52（t-48）再除以49 对于50-50，之前乘以51（t-49）再除以50，然后再除以2。

此方程适用于任何投掷次数。

步骤3：对这18个值进行17自由度的卡方检验，得到结果p值。

当p值大于0.999时，接近完美。随机数发生器是否会太过于接近完美？是的，太容易预测了。在0.001以下的范围内通常会出现明显问题。一个测试套件将小数点右侧的300个零视为微不足道的错误，而10-14个连续的零则相当糟糕。有些人认为6个零已经足以被视为明确的失败。出于安全考虑，有些人认为1或2个零就足够了，但其实是错误的。因此，为了获得优秀随机数发生器的p值低于0.01，需要采取多组会话。

步骤4：将p值输入到0-1.0直线Kolmogorov-Smirnov测试中。不同的专家建议将输入数量设置为10至1000。100还不够。200可以。500稍微过于激进。

下面是获取K-S最大差异的伪代码：

Set low := 0;  Set n := 200;  
Set ansForward := 0; Set ansBack := 0;

sort( pval [n] );
for (j := 0; j < n; j := j+1)   
 {  Set Kback := pval [ j ] - low;
    Set low := low +1 / n;    { Ranges from 0 to 1 }
    Set Kforward := low - pval [ j ];  
    if (Kforward > ansForward) Set ansForward := Kforward;
    if (Kback > ansBack) Set ansBack := Kback;
   }
{ Separate analysis can perhaps be made here on ansForward and ansBack.  Someone like Peter Brand might also examine and magnify the bottom 5% and the top 5%. }
if (ansForward > ansBack)
      return ansForward;
else
      return ansBack;   ∎

K-S答案不是p值，对于200个p值，不应超过0.115。0.03到0.08对于好的RNG来说是正常的。0.115到0.13是可疑的。K-S测试非常简单，也相当有效。上面展示了一个优秀的新有序频率测试。任何未通过此测试的RNG都不应再进行测试，并立即更换。但是，接下来呢？OFTest不能取代LOR测试。建议使用样本量为200,000、自由度为15的Runs长度测试，将其输入K-S测试中200次。 （请注意，“大于j”的最小LOR箱的预期总数等于第j个箱。）然后呢？对于许多游戏来说，这两个测试就足够了。从NIST、Diehard、Dieharder、Crusher中有很多选择。（注：Diehard Overlapping Sums测试既不优秀也存在缺陷，不是Marsaglia原始Fortran代码的忠实解释。）一些n=200的RNG的结果。

  1. LCG 134775813x + 1模2^31种子=11111： 高位：OFT KS：0.0841通过。LOR KS：0.04786通过。前200,000个数的单比特：-189通过。 第16位：OFT KS：0.5477失败。前200,000个数的单比特：114通过。 所有从0到15位的比特均未通过OFT测试，但通过了单比特测试。

  2. 常被诟病的LCG Randu：65539x + 0模2^31种子=11111： 高位：OFT KS：0.03567 LOR KS：0.07709。前200,000个数的单比特：-165 第18位：OFT KS：0.15143 前200,000个数的单比特：+204 所有从0到17位的比特均未通过OFT测试。

  3. LCG 69069x + 1模2^32种子=11111： 高位：OFT KS：0.05547 LOR KS：0.0456 前200,000个数的单比特：-290 第17位：OFT KS：0.1467 前200,000个数的单比特：-193 所有从0到13位的比特均未通过OFT测试。

  4. LCG 3141592653x + 2718281829模2^35种子=11111： 高位：OFT KS：0.02868 LOR KS：0.06117 前200,000个数的单比特：-69 第16位：OFT KS：0.240 前200,000个数的单比特：-13 所有从0到15位的比特均未通过OFT测试。

  5. LCG 23x + 0模2^27种子=11111： 高位：OFT KS：0.5368 前200,000个数的单比特：-235 所有比特均未通过OFT测试。

请注意，任何LCG的低位应从返回结果中丢弃。
关于2^35的说明：这是任何RNG的最小周期和显着性，因为硬币翻转、掷骰子等事情可能会连续发生30次，但不太可能发生35次。2^32的周期不足，对于现实生活中的情况来说太小了。
LWAP
1
“LWAP” 是什么意思？ - Ursa Major
5
如何确保生成的数字是随机的。
你无法“确保”，没有办法用有限数量的测试来确定任何函数与随机数生成器之间的区别。但你可以进行统计分析：
因此，如果无法明确证明随机性，我们可以采取什么措施呢？实际的方法是从给定的生成器中获取许多随机数序列，并将它们提交给一系列统计测试。随着序列通过更多的测试，对数字随机性的信心增强，对生成器的信心也增强。然而，由于我们期望某些序列看起来不随机（例如我们的骰子上的十次六点），我们应该预计一些序列至少会失败一些测试。然而，如果许多序列未能通过测试，我们就应该持怀疑态度。这也是您直观地测试骰子是否被加重的方法：投掷多次，如果您看到太多相同值的序列出现，您应该持怀疑态度。

详见Charmaine Kenny的研究部分，了解可运行的测试更多细节。

4
这是英文原文的翻译：

这是一件非常困难的事情。

你可以尝试使用ENT和Fourmilab，并将其与他们的RNG HotBits 的结果进行比较。你也可以查看Random.org。

这个看起来也很有趣：Diehard tests（不过我没有使用过它）。

5
Diehard测试套件已经不再维护，已被NIST测试用于随机数的测试套件所取代。请参见http://www.random.org/analysis/#2005。 - Pascal Thivent
+1 给“这是非常困难的事情”。仅包括其他回答者建议的一些简单的单项或双项测试是远远不够的。实际上，这是如此困难的事情，除非你跟上最新的研究发现（而你在SO上的问题表明你没有），否则你可能会更好地使用现有的PRNG而不是尝试自己实现。更好，但没那么有趣。 - High Performance Mark
3
有一个非常好用的工具可以做到这一点：http://www.phy.duke.edu/~rgb/General/dieharder.php。例如，您可以测试内置的urandom。
cat /dev/random | dieharder -a -g 200

或者编写自己的脚本，创建一个带有随机数字的文件

dieharder -a -g 202 -f random.txt
2

仅仅因为随机数是随机的，你无法确保数字是随机的。

获得一百万个连续的9的字符串的概率与获得任何其他特定的一百万个字符长的序列相同。您可以检查的唯一一件事是正确分布在大样本集上。运行一个规模可观的测试，并计算每种可能结果的相对出现次数。

在足够大的样本中，它们应该大致相同。

另一个可能性是测试不可重复性。理想情况下，随机数不应依赖于之前的数字。非常简单（线性同余）的伪随机数生成器最终很可能会给您相同的数字序列，但在足够大的集合中，您可能不会关心（除非您非常关注随机性）。

2

这取决于你对随机性的要求有多严格。如果不是太严格，我通常会生成大量随机数，找到它们的频率，然后使用类似于Open Office中的电子表格来绘制一个图形。如果分布看起来正常，那么我就可以使用它。

1
0

除非您可以访问随机数生成器并使用它随意生成数字，否则您无法测试数字序列是否随机。想一想：您有一个随机数生成器。假设它是一个均匀分布的随机数生成器，在范围[0,9]内生成随机整数。给定一个序列：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

你能判断它是否是随机的吗？我们的均匀随机数生成器有一个有限的概率10−10会生成这个确切的序列。事实上，对于任何长度为10的序列，我们的均匀随机数生成器生成该序列的概率相同。因此，根据定义，您无法确定给定序列是否随机。

如果您可以访问生成器本身并可以使用它来生成多个序列，则检查随机性是有意义的。为此，我会看Diehard tests。有各种实现。

为什么您不能访问要测试的 PRNG？所有随机性测试当然都会大量使用它们正在测试的 PRNG，并对生成的数字序列执行各种测试，例如您引用的 DieHard 测试。 - arainone
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接