如何测试随机性（例如：洗牌）

洗牌很多，然后记录结果（如果我没看错的话）。我记得看到过“随机数生成器”的比较。他们只是一遍又一遍地测试它，然后将结果绘制成图表。

如果它真的是随机的，则图形将大部分是偶数的。

测试随机性的唯一方法是编写一个程序，尝试为被测试的数据构建一个预测模型，然后使用该模型尝试预测未来的数据，然后表明其预测的不确定性或熵随着时间的推移趋向于最大（即均匀分布）。当然，你总是不确定你的模型是否已经捕获了所有必要的上下文;给定一个模型，总是可以构建第二个模型，该模型生成与第一个模型相比看起来是随机的非随机数据。但只要你接受冥王星的轨道对洗牌算法的结果影响不大，那么你应该能够确信它的结果是可以接受的随机的。

当然，如果你这样做，你不妨以生成方式使用你的模型，以实际创建你想要的数据。如果你这样做了，那么你就回到了原点。

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

至于洗牌算法，请使用众所周知的算法，例如 Fisher-Yates（又名“Knuth Shuffle”）。只要底层 RNG 是均匀随机的，洗牌将是均匀随机的。如果您使用的是 Java，则此算法在标准库中可用（请参阅 Collections.shuffle）。

对于大多数应用程序来说，这可能无关紧要，但请注意，大多数 RNG 没有提供足够的自由度来产生 52 张牌组的所有可能的排列（此处解释）。

我没有完全听从你的问题。你说

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

你是什么意思？如果你假设你可以生成随机性，那就没有必要测试它。

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

困难的问题是你是否可以信任你的RNG。下面是一个示例链接，指向在特定上下文中讨论该问题的人。

首先，不可能确定某个有限的输出是否是“真正随机的”，因为正如你所指出的，任何输出都是可能的。

可以做的是获取一系列输出，并根据更有可能的测量值检查该序列的各种测量值。您可以得出一种置信度分数，表明生成算法做得很好。

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

但我们不应该止步于此！因为这个算法可能会被一个只在两个洗牌之间交替的系统所愚弄，这些洗牌旨在在每个位置给出 25.5 的精确平均值。我们怎样才能做得更好？

我们期望在不同的洗牌中，每个位置的均匀分布（任何给定牌的可能性相等）。因此，在 10 次洗牌中，我们可以尝试验证这些选择是否“看起来一致”。这基本上只是原始问题的简化版本。您可以检查标准偏差是否合理，最小值是否合理，以及最大值是否合理。您还可以检查其他值，例如最接近的两张卡片（按我们分配的数字）是否也有意义。

但是我们也不能像这样无限地添加各种测量值，因为，如果有足够的统计数据，由于某种原因，任何特定的洗牌都显得极不可能（例如，这是为数不多的洗牌之一，其中卡片X，Y，Z按顺序出现）。因此，最大的问题是：哪一组是正确的测量方法？在这里我不得不承认，我不知道最好的答案。然而，如果你有一个特定的应用，你可以选择一组好的属性/测量来测试，并使用它们——这似乎是密码学家处理事情的方式。

有很多关于测试随机性的理论。对于洗牌算法的非常简单的测试，您可以进行大量洗牌，然后运行卡方检验，即每张牌出现在任何位置的概率都是均匀的。但这并不能测试连续的卡片是否不相关，所以你也想对此进行测试。

Knuth's Art of Computer Programming 的第 2 卷提供了许多测试，您可以在 3.3.2（实证测试）和 3.3.4（频谱测试）部分以及它们背后的理论中使用。

测试 52！当然，可能性是不可能的。相反，请尝试在较少数量的牌上洗牌，例如 3、5 和 10。然后，您可以测试数十亿次随机排列，并使用直方图和卡方统计检验来证明每个排列都出现了“偶数”次。

到目前为止没有代码，因此我从我对原始问题的回答中复制粘贴了一个测试部分。

  // ...
  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随机性是一门科学。

这是您可以执行的一项简单检查。它使用生成的随机数来估计 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;
}

我自己思考一下，我会做的是这样的：

设置（伪代码）

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

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

为了快速测试，您可以随时尝试压缩它。一旦它没有压缩，那么你就可以继续进行其他测试。

我试过更努力，但它拒绝洗牌。所有测试均失败。它也非常笨拙，它不会让您指定所需的值范围或类似的东西。