如何testing随机性（例如 – Shuffling）
首先，这个问题是从这个问题中剔除的。 我这样做是因为我认为这部分比较长问题的一个子部分更大。 如果冒犯了，请原谅我。
假设你有一个产生随机性的algorithm。 现在你怎么testing它？ 或者更直接 – 假设你有一套洗牌的algorithm，你怎么testing它是一个完全随机的algorithm？
给这个问题添加一些理论 – 一副牌可以在52中洗牌！ （52阶乘）不同的方式。 拿一副牌，手工洗牌，记下所有牌的顺序。 你会得到这个洗牌的概率是多less？ 答案：1/52！
在洗牌后，你有什么机会按顺序获得每套花色的A，K，Q，J …？ 答案1/52！
所以，只要洗牌一次，看看结果就不会给你任何有关洗牌algorithm随机性的信息。 两次，你有更多的信息，三更甚至…
你将如何黑箱testing随机性洗牌algorithm？
统计。 testingRNG的事实标准是Diehard套件 。 另外， Ent程序提供的解释比较简单，但不太全面。
至于洗牌algorithm，使用一个众所周知的algorithm，如Fisher-Yates （又名“Knuth Shuffle”）。 只要潜在的RNG是一致随机的，随机洗牌将是均匀随机的。 如果您正在使用Java，则此algorithm在标准库中可用（请参阅Collections.shuffle ）。
对于大多数应用程序来说，这可能并不重要，但请注意，大多数RNG不能提供足够的自由度来生成52张牌的每一种可能的排列（ 在此解释）。
这是一个简单的检查，你可以执行。 它使用生成的随机数来估计Pi。 这不是随机性的certificate，但可怜的RNG通常不会很好（他们会返回类似2.5或3.8而不是3.14）。
理想情况下，这只是你将运行检查随机性的许多testing之一。
你可以检查的其他东西是输出的标准偏差 。 在0..n范围内均匀分布的值总体的预期标准差接近n / sqrt（12）。
/** * This is a rudimentary check to ensure that the output of a given RNG * is approximately uniformly distributed. If the RNG output is not * uniformly distributed, this method will return a poor estimate for the * value of pi. * @param rng The RNG to test. * @param iterations The number of random points to generate for use in the * calculation. This value needs to be sufficiently large in order to * produce a reasonably accurate result (assuming the RNG is uniform). * Less than 10,000 is not particularly useful. 100,000 should be sufficient. * @return An approximation of pi generated using the provided RNG. */ public static double calculateMonteCarloValueForPi(Random rng, int iterations) { // Assumes a quadrant of a circle of radius 1, bounded by a box with // sides of length 1. The area of the square is therefore 1 square unit // and the area of the quadrant is (pi * r^2) / 4. int totalInsideQuadrant = 0; // Generate the specified number of random points and count how many fall // within the quadrant and how many do not. We expect the number of points // in the quadrant (expressed as a fraction of the total number of points) // to be pi/4. Therefore pi = 4 * ratio. for (int i = 0; i < iterations; i++) { double x = rng.nextDouble(); double y = rng.nextDouble(); if (isInQuadrant(x, y)) { ++totalInsideQuadrant; } } // From these figures we can deduce an approximate value for Pi. return 4 * ((double) totalInsideQuadrant / iterations); } /** * Uses Pythagoras' theorem to determine whether the specified coordinates * fall within the area of the quadrant of a circle of radius 1 that is * centered on the origin. * @param x The x-coordinate of the point (must be between 0 and 1). * @param y The y-coordinate of the point (must be between 0 and 1). * @return True if the point is within the quadrant, false otherwise. */ private static boolean isInQuadrant(double x, double y) { double distance = Math.sqrt((x * x) + (y * y)); return distance <= 1; } 首先，如果某个有限的输出是“真正的随机”，那么就不可能知道，因为正如你所指出的那样， 任何输出都是可能的 。
可以做什么，是采取一系列的输出，并检查更可能的这个序列的各种测量。 你可以得到一个信心评分，生成algorithm做得很好。
例如，你可以检查10个不同的洗牌的输出。 为每张卡片分配一个0-51的数字，并把卡片的平均值放在洗牌中的位置6。 收敛的平均值是25.5，所以在这里你会看到1的值。 你可以使用中心极限定理来估计每个平均值对于给定位置的可能性。
但是，我们不应该停留在这里！ 因为这个algorithm可能被一个只在两个洗牌之间交替的系统所愚弄，这个洗牌被devise成在每个位置给出25.5的精确平均值。 我们怎样才能做得更好？
我们期望在不同的洗牌中，每个位置的统一分配（对于任何给定的卡片具有相同的可能性）。 所以在10次洗牌中，我们可以试着去validation这个select是否“统一”。 这基本上只是原始问题的简化版本。 你可以检查标准偏差是否合理，最小值是否合理，最大值是多less。 你也可以检查其他值，比如最接近的两张牌（由我们指定的号码），也是有意义的。
但是，我们也不能仅仅添加像这样的无限次数的测量，因为给定足够的统计数据，任何特定的混洗会由于某种原因而显得不太可能（例如，这是卡X，Y，Z出现在其中的less数洗牌之一订购）。 所以最大的问题是：哪一个测量是正确的？ 在这里，我不得不承认，我不知道最好的答案。 但是，如果你有一个特定的应用程序，你可以select一组好的属性/度量来testing，并与这些 – 这似乎是密码学家处理的方式。
关于随机性testing有很多理论。 对于卡洗牌algorithm的一个非常简单的testing，你可以做很多洗牌，然后进行卡方检验，每张卡在任何位置上翻的概率是一致的。 但是这并不能certificate连续的卡片是不相关的，所以你也想做一些testing。
Knuth的“计算机编程艺术”第2卷给出了一些可以在第3.3.2节（经验testing）和第3.3.4节（频谱testing）中使用的testing以及它们背后的理论。
随机洗牌，然后logging结果（如果即时读取正确）。 我记得看过“随机数发生器”的比较。 他们只是反复testing，然后绘制结果。
如果真的是随机的，那么graphics将大部分是平坦的。
testing随机性的唯一方法是编写一个程序，试图为正在testing的数据build立预测模型，然后使用该模型来尝试预测未来的数据，然后显示其预测的不确定性或熵倾向于随着时间的推移而达到最大（即均匀分布）。 当然，你总是不确定你的模型是否已经捕获了所有必要的上下文; 给定一个模型，总是可以build立第二个模型，生成非随机的数据，这个数据看起来是随机的。 但只要你接受冥王星的轨道对洗牌algorithm的结果有微不足道的影响，那么你应该能够满足自己的结果是可接受的随机。
当然，如果你这样做的话，你也可以使用你的模型来生成你想要的数据。 如果你这样做，那么你又回到了原点。
我没有完全遵循你的问题。 你说
假设你有一个产生随机性的algorithm。 现在你怎么testing它？
你什么意思？ 如果你假设你可以产生随机性，那么不需要testing它。
一旦你有一个好的随机数发生器，创build一个随机排列是很容易的（例如，打电话给你的卡1-52。生成52个随机数，每个卡按顺序分配，然后根据你的52个随机数进行sorting）。 你不会通过产生你的排列来破坏你的好RNG的随机性。
难题是你能否信任你的RNG。 以下是在特定情况下讨论该问题的人员的示例链接。
testing52！ 可能性当然是不可能的。 相反，你可以尝试在较小数量的卡片上进行洗牌，比如3,5和10.然后，你可以testing数十亿次洗牌，并使用直方图和卡方统计检验来certificate每个排列是“偶数”的时代。
到目前为止没有任何代码，因此我从我的答案复制粘贴testing部分到原始问题。
// ... int main() { typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map; Map freqs; Deck d; const size_t ntests = 100000; // compute frequencies of events: card at position for (size_t i = 0; i < ntests; ++i) { d.shuffle(); size_t pos = 0; for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos) ++freqs[std::make_pair(pos, *j)]; } // if Deck.shuffle() is correct then all frequencies must be similar for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j) std::cout << "pos=" << j->first.first << " card=" << j->first.second << " freq=" << j->second << std::endl; }
此代码不testing潜在的伪随机数生成器的随机性。 testingPRNG随机性是科学的一个分支。
自己想，我会做的是这样的：
设置（伪码）
// A card has a Number 0-51 and a position 0-51 int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values ShuffleCards(); ForEach (card in Cards) { StatMatrix[Card.Position][Card.Number]++; }
这给了我们一个matrix52x52，表示卡在某个位置结束了多less次。 重复这个很多次（我会从1000开始，但是统计比我更好的人可能会给出更好的数字）。
分析matrix
如果我们拥有完美的随机性，并且无限次地执行洗牌，那么对于每张牌以及对于每个位置来说，卡在该位置结束的次数与任何其他卡相同。 用不同的方式说同样的话：
statMatrix[position][card] / numberOfShuffle = 1/52.
所以我会计算一下这个数字有多远
在随机事件之前查看你的输出与你的输出相比较。 这是我做的一个例子。
public void testShuffleRemainingDeck() { System.out.println("ShuffleRemainingDeck"); Deck instance = new Deck(true); //create new deck System.out.println(instance.toString()); //print unshuffled deck. instance.ShuffleRemainingDeck(); //shuffle the deck. System.out.println(instance.toString()); //print shuffled deck. //now visually compare the outputs. }
对于一个快速testing，你总是可以尝试压缩它。 一旦它不压缩，那么你可以移动到其他testing。
我已经尝试了dieharder，但它拒绝为洗牌工作。 所有testing失败。 它也非常笨重，它不会让你指定你想要的值的范围或类似的东西。
