如何测试随机性(以点洗牌为例)

统计数字测试RNG的实际标准是 Diehard suite (原载于 http://stat.fsu.edu/pub/diehard Ent program 提供更易于解释但不太全面的测试。

Fisher-Yates (又称“克努斯洗牌”)。只要基础RNG是一致随机的,洗牌将是一致随机的。如果您使用的是Java,这个算法可以在标准库中找到(参见 Collections.shuffle

here

理想情况下,这只是您将运行以检查随机性的许多测试之一。

您可以检查的其他内容是 standard deviation

/**
 * 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;
}

首先,不可能确定某个有限的输出是否是“真正随机的”,因为正如你所指出的, any output is possible .

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

但我们不应该停在这里!因为这个算法可能会被一个只在两次洗牌之间交替的系统所愚弄,这两次洗牌的目的是在每个位置给出25.5的精确平均值。我们怎样才能做得更好?

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

有很多关于测试随机性的理论。对于一个非常简单的卡片洗牌算法测试,你可以进行大量的洗牌,然后进行卡方检验,确定每张卡片出现在任何位置的概率是一致的。但这并不能测试连续的卡片是否不相关,所以您还需要对其进行测试。

Knuth的《计算机编程艺术》第2卷提供了许多测试,您可以在第3.3.2节(经验测试)和第3.3.4节(光谱测试)中使用这些测试以及它们背后的理论。

测试随机性的唯一方法是编写一个程序,尝试为被测数据建立一个预测模型,然后使用该模型尝试预测未来数据,然后显示其预测的不确定性或熵随时间趋于最大(即均匀分布)。当然,您总是不确定您的模型是否捕获了所有必要的上下文;给定一个模型,总是可以构建第二个模型,生成第一个模型看起来随机的非随机数据。但是,只要你接受冥王星的轨道对洗牌算法的结果影响很小,那么你就应该能够满足自己,它的结果是可以接受的随机的。

当然,如果您这样做,您还可以使用您的模型 生成的 ,以实际创建所需的数据。如果你这么做了,你就回到了原点。

如果它真的是随机的,那么图形将基本上是均匀的。

我没有完全明白你的问题。你说

假设您有一个生成随机性的算法。现在如何测试它?

什么意思?如果你假设你能产生随机性,就没有必要去测试它。

一旦你有了一个好的随机数生成器,创建一个随机排列就很容易了(例如,将你的卡片称为1-52。生成52个随机数,将每个随机数按顺序分配给一张卡片,然后根据52个随机数进行排序)。您不会通过生成排列来破坏好RNG的随机性。

困难的问题是你是否能信任你的RNG。 Here's 指向在特定上下文中讨论该问题的人的示例链接。

测试52!可能性当然是不可能的。取而代之的是,在较小数量的牌上尝试洗牌,比如3、5和10。然后,您可以测试数十亿次洗牌,并使用直方图和卡方统计测试来证明每个排列出现的次数是“偶数”。

到目前为止还没有代码,因此我从中复制粘贴了一个测试部分 my answer

  // ...
  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;    
  }

此代码不测试底层伪随机数生成器的随机性。测试PRNG随机性是整个科学的一个分支。

我已经努力了,但它拒绝洗牌。所有测试都失败了。它也非常单调,它不允许您指定所需的值的范围或类似的内容。

我自己想一想,我会这样做:

设置(伪代码)

// 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]++;
}

这为我们提供了一个矩阵52x52,指示一张卡在某个位置结束了多少次。重复这一点很多次(我会从1000开始,但比我更擅长统计的人可能会给出一个更好的数字)。

分析矩阵

如果我们有完美的随机性,并执行洗牌无限次,那么对于每张牌和每个位置,牌在该位置结束的次数与任何其他牌相同。用不同的方式说同样的话:

statMatrix[position][card] / numberOfShuffle = 1/52.

所以我会计算我们离这个数字有多远。