如何测试随机性(以点为例-改组) [英] 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是一致随机的，则随机播放将是一致随机的.如果您使用的是Java，则标准库中提供了此算法(请参见

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屋！