如何证明一个随机数发生器比另一个好？

Question

你如何证明一个RNG优于另一个？

我并不是说在运行时间方面,而是"生成"的熵量 - 它也在周期性概念中滚动(低周期=低熵).

RNG可以证明是最佳的吗？或者这是一个无法实现的目标？通过最优,我的意思是任何序列同样可能并且独立于过去或未来的结果.

我对算法感兴趣,而不是宇宙背景采样设备或其他物理"随机性"来源(它是随机的还是复杂的？)

Answer 1

见http://www.random.org/analysis/

唯一的最佳RNG:

Answer 2

美国国家标准与技术研究院对此有一些很好的信息:

http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

看起来有一个测试套件和许多好的参考资料

Answer 3

旧的测试标准曾经是“顽固测试”。http://en.wikipedia.org/wiki/Diehard_tests这已被 DKnight 指出的 NIST 测试取代：http://csrc.nist.gov/groups/ST/toolkit/rng/index.html。Diehard 维基文章为您提供了所关注事物类型的良好概述。NIST 还需要更多的挖掘。

正如您所说，没有任何伪 RNG（算法）可以被证明是最佳的。它们都有一个种子值，并依赖于输入来生成值。如果您知道种子和状态，您就知道下一个值。例如，请查看http://en.wikipedia.org/wiki/Mersenne_twister。我喜欢它主要是因为它的名字很棒，但这篇文章很好地解释了 PRNG 的原理。