如何测试随机性(例如 - 洗牌) [英] How to test randomness (case in point - Shuffling)

问题描述

首先，这个问题是从这个问题中删除的.我这样做是因为我认为这部分比较长问题的子部分要大.如有冒犯，请见谅.

First off, this question is ripped out from this question. I did it because I think this part is bigger than a sub-part of a longer question. If it offends, please pardon me.

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

Assume that you have a algorithm that generates randomness. Now how do you test it? Or to be more direct - Assume you have an algorithm that shuffles a deck of cards, how do you test that it's a perfectly random algorithm?

为问题添加一些理论-一副牌可以洗52次！(52阶乘)不同的方式.拿一副牌，用手洗牌，写下所有牌的顺序.你得到那次洗牌的概率是多少?答案:1/52！

To add some theory to the problem - A deck of cards can be shuffled in 52! (52 factorial) different ways. Take a deck of cards, shuffle it by hand and write down the order of all cards. What is the probability that you would have gotten exactly that shuffle? Answer: 1 / 52!.

在洗牌后，您将获得 A、K、Q、J……的每个花色序列中的机会是多少?答案 1/52！

What is the chance that you, after shuffling, will get A, K, Q, J ... of each suit in a sequence? Answer 1 / 52!

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

So, just shuffling once and looking at the result will give you absolutely no information about your shuffling algorithms randomness. Twice and you have more information, Three even more...

您将如何黑盒测试随机性的改组算法?

How would you black box test a shuffling algorithm for randomness?

推荐答案

统计.测试 RNG 的实际标准是 Diehard 套件(最初可在 http://stat.fsu.edu/pub/diehard).或者，Ent 程序 提供了更易于解释但不太全面的测试.

Statistics. The de facto standard for testing RNGs is the Diehard suite (originally available at http://stat.fsu.edu/pub/diehard). Alternatively, the Ent program provides tests that are simpler to interpret but less comprehensive.

至于改组算法，请使用众所周知的算法，例如 Fisher-Yates(又名Knuth Shuffle").只要底层 RNG 是均匀随机的，shuffle 将是均匀随机的.如果您使用的是 Java，则该算法在标准库中可用(请参阅 Collections.shuffle).

As for shuffling algorithms, use a well-known algorithm such as Fisher-Yates (a.k.a "Knuth Shuffle"). The shuffle will be uniformly random so long as the underlying RNG is uniformly random. If you are using Java, this algorithm is available in the standard library (see Collections.shuffle).

对于大多数应用程序来说这可能无关紧要，但请注意，大多数 RNG 没有提供足够的自由度来生成 52 张牌的所有可能的排列(解释 此处).

It probably doesn't matter for most applications, but be aware that most RNGs do not provide sufficient degrees of freedom to produce every possible permutation of a 52-card deck (explained here).

这篇关于如何测试随机性(例如 - 洗牌)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！