如何测试随机性(例如 - 改组)

Question

首先,这个问题从这个问题中被删除了.我这样做是因为我认为这部分比一个较长问题的一部分要大.如果它冒犯了,请原谅我.

假设您有一个生成随机性的算法.现在你如何测试它？或者更直接 - 假设你有一个混合了一副牌的算法,你如何测试它是一个完全随机的算法？

为问题添加一些理论 - 一副牌可以在52中洗牌!(52阶乘)不同的方式.拿一副纸牌,手工洗牌,记下所有牌的顺序.你有什么可能得到这种洗牌的概率是多少？答案:1/52!

在洗牌之后,你在每个套装中获得A,K,Q,J ......的几率是多少？回答1/52!

所以,只需改组一次并查看结果就可以完全没有关于您的改组算法随机性的信息.两次,你有更多的信息,三个甚至更多......

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

Answer 1

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

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

对于大多数应用来说,这可能并不重要,但请注意,大多数RNG没有提供足够的自由度来产生52张牌的每种可能的排列(在此解释).

Answer 2

这是您可以执行的一项简单检查.它使用生成的随机数来估计Pi.它不是随机性的证据,但是不好的RNG通常不能很好地完成(它们会返回2.5或3.8而不是3.14).

理想情况下,这只是您为检查随机性而运行的众多测试之一.

您可以检查的其他内容是输出的标准偏差.均匀分布的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;
}

Answer 3

首先,不可能确定某个有限输出是否"真正随机",因为正如你所指出的那样,任何输出都是可能的.

可以做的是采取一系列输出并检查该序列的各种测量结果.你可以得出一种置信度得分,即生成算法做得很好.

例如,您可以检查10个不同shuffle的输出.为每张卡分配一个数字0-51,并在洗牌时取出位置6的卡的平均值.收敛平均值为25.5,所以你会惊讶地看到这里的值为1.您可以使用中心极限定理来估计给定位置的每个平均值的可能性.

但我们不应该止步于此!因为这个算法可能被一个只在两个混洗之间交替的系统所欺骗,这两个混洗被设计成在每个位置给出25.5的精确平均值.我们怎样才能做得更好？

我们期望在不同的洗牌中,每个位置的均匀分布(任何给定卡的可能性相等).因此,在10次洗牌中,我们可以尝试验证这些选择看起来是否均匀.这基本上只是原始问题的简化版本.您可以检查标准偏差是否合理,min是否合理,以及最大值.您还可以检查其他值,例如最近的两张卡(按我们指定的号码),也是有意义的.

但是我们也不能像这样无限制地添加各种测量,因为,如果给出足够的统计数据,任何特定的随机播放都会因某种原因出现的可能性很小(例如,这是卡片X,Y,Z出现的极少数洗牌之一)订购).所以最大的问题是:哪种测量方法正确？在这里,我不得不承认我不知道最好的答案.但是,如果你有一个特定的应用程序,你可以选择一组好的属性/测量来测试,并使用它们 - 这似乎是密码学家处理事情的方式.