如何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失败。 它也非常笨重,它不会让你指定你想要的值的范围或类似的东西。