algorithm - 证明随机生成的数字是均匀分布的

Question

我在面试中被问到这个问题。

Given a random number generator to generate a number between [0,N), how to prove this number is uniform distributed.

我不确定如何解决这个问题，有什么建议吗？

Answer 1

要证明它，您需要知道所使用的算法并以图形方式显示所有状态的集合构成一个循环，没有子循环，并且状态的基数空间模 N 为零，因此没有一组状态比其他状态更频繁/更不频繁出现。例如，这就是我们如何知道 Mersenne Twister 是均匀分布的，即使 64 位版本的周期长度为 2¹⁹⁹³⁷-1 并且在宇宙的生命周期内永远无法枚举。

否则，您将使用统计检验来检验均匀性假设。统计数据不能证明一个结果，它不能反驳假设。您的样本量越大，覆盖假设的失败就越令人信服，但这永远不是证据。 (这种观点导致与非统计学家/非科学家的沟通问题比我所知道的任何其他问题都要多。)有许多一致性检验，包括卡方检验、Anderson-Darling 和 Kolmogorov-Smirnov 等等。

所有均匀性测试都将通过值序列，例如 0,1,2,...,N-1,0,1,... 因此均匀性不足以说明您拥有一个好的生成器。您还应该通过间距测试、上升/下降、高于/低于平均值、“生日”测试等测试来测试序列相关性。

George Marsaglia 在他的职业生涯中创建了一套非常全面的均匀性和序列相关性测试，并于 1995 年发表，他戏称为“Diehard tests”(因为它是一组重型测试).