math - 如何测试随机性(例如 - 洗牌)

Question

首先，这个问题是从 this 中摘下来的问题。我这样做是因为我认为这部分比较长问题的子部分更大。如有冒犯，请见谅。

假设您有一个生成随机性的算法。现在你如何测试它？或者更直接地说 - 假设您有一个洗牌的算法，您如何测试它是一个完全随机的算法？

为问题添加一些理论 -一副牌可以洗52张! (52 阶乘)不同的方式。拿一副牌，用手洗牌并记下所有牌的顺序。您完全得到该洗牌的概率是多少？答案:1/52!.

洗牌后，您按顺序获得每种花色的 A、K、Q、J ... 的机会有多大？回答 1/52!

因此，只需洗牌一次并查看结果，您绝对不会获得有关洗牌算法随机性的信息。两次，您可以获得更多信息，三次甚至更多......

如何黑盒测试洗牌算法的随机性？

Answer 1

统计数据。测试 RNG 的事实上的标准是 Diehard suite (最初可在 http://stat.fsu.edu/pub/diehard 获取)。或者，Ent program提供的测试更容易解释，但不太全面。

至于洗牌算法，请使用众所周知的算法，例如 Fisher-Yates (又名“高德纳洗牌”)。只要底层 RNG 是均匀随机的，洗牌就会是均匀随机的。如果您使用 Java，则标准库中提供了此算法(请参阅 Collections.shuffle)。

这对于大多数应用程序来说可能并不重要，但请注意，大多数 RNG 并没有提供足够的自由度来生成 52 张牌的每种可能的排列(解释 here )。