algorithm - 随机数发生器测试

Question

您将如何测试随机数生成器是否正在生成实际的随机数？

我的方法:首先构建一个大小为 M 的哈希，其中 M 是质数。然后拿号 由随机数生成器产生，并用M取模。 并看到它填充了所有哈希值或仅填充了一部分。 这就是我的方法。我们可以用可视化来证明吗？

因为我对测试的了解非常少。你能建议我彻底解决这个问题吗？提前致谢

Answer 1

您应该知道，您不能保证随机数生成器正常工作。请注意，即使是 [1,10] 范围内的完美均匀分布 - 在 10 个数字的随机抽样中，有 10^-10 的机会得到 10 乘以 10。

有可能吗？当然不是。

那么 - 我们可以做什么？

如果随机数生成器确实均匀分布，我们可以统计证明组合 (10,10,....,10) 不太可能。这个概念叫做 Hypothesis testing 。通过这种方法，我们可以说“确定性水平为 x% - 我们可以拒绝数据取自均匀分布的假设”。

一种常用的方法是使用 Pearson's Chi-Squared test ，这个想法与你的相似 - 你填写一个表格 - 检查每个单元格的观察到的(生成的)数字数量是多少，预期是多少 em> 零假设下每个单元格的数字数量(在您的情况下，预期为 k/M - 其中 M 是范围的大小，k 是采用的数字总数)。
然后您对数据进行一些操作(有关此操作的详细信息，请参阅维基百科文章)- 并获得一个数字(测试统计数据)。然后你检查这个数字是否可能来自Chi-Square Distribution .如果是 - 您不能拒绝零假设，如果不是 - 您可以 x% 确定数据不是从均匀随机生成器中获取的。

编辑:示例:
你有一个立方体，你想检查它是否“公平”(在 [1,6] 中均匀分布)。将其抛出 200 次(例如)并创建下表:

number:                1       2         3         4          5          6
empirical occurances: 37       41        30        27         32         33
expected occurances: 33.3      33.3      33.3      33.3       33.3       33.3

现在，根据 Pearson 的检验，统计数据为:

X = ((37-33.3)^2)/33.3 + ((41-33.3)^2)/33.3 + ... + ((33-33.3)^2)/33.3 
X = (18.49 + 59.29 + 10.89 + 39.69 + 1.69 + 0.09) / 33.3
X = 3.9

随机C~ChiSquare(5) , 高于 3.9 的概率是~0.45 (这并非不可能)¹。

所以我们不能拒绝零假设，我们可以得出结论，数据可能均匀分布在[1,6]中。

---

(1) 如果值小于 0.05，我们通常会拒绝原假设，但这取决于具体情况。