首页 / 知识

关于数学：如何测试随机性(以点为例-改组)

2023-04-14 23:18:00

How to test randomness (case in point - Shuffling)

首先，从这个问题中剔除掉这个问题。我这样做是因为我认为这部分内容比一个较长问题的子部分要大。如果冒犯了，请原谅我。

假设您有一个生成随机性的算法。现在如何测试？
或者更直接一点-假设您有一种算法可以随机播放一副纸牌，那么如何测试它是完全随机的算法呢？

为该问题添加一些理论-
一副纸牌可以在52中洗牌！ (52阶乘)不同的方式。拿一副纸牌，用手将其洗牌并写下所有纸牌的顺序。您将完全洗牌的概率是多少？答案：1/52!。

改组后，您有机会获得序列中每个西装的A，K，Q，J ...的机会是什么？回答1/52！

因此，仅洗牌一次并查看结果绝对不会给您关于洗牌算法随机性的任何信息。您有两次获得更多信息，甚至还有三个...

黑匣子将如何测试混洗算法的随机性？

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

至于混排算法，请使用众所周知的算法，例如Fisher-Yates(也称为" Knuth Shuffle")。只要基础RNG是一致随机的，则随机播放将是一致随机的。如果您使用的是Java，则该算法在标准库中可用(请参阅Collections.shuffle)。

对于大多数应用程序来说，这可能无关紧要，但是请注意，大多数RNG不能提供足够的自由度来生成52张卡片组的所有可能排列(在此进行解释)。

这是您可以执行的一项简单检查。它使用生成的随机数来估计Pi。这不是随机性的证明，但是劣质的RNG通常在其上效果不佳(它们将返回2.5或3.8而不是?3.14的值)。

理想情况下，这只是您要检查随机性的众多测试之一。

您可以检查的其他内容是输出的标准偏差。范围为0..n的值的均匀分布总体的预期标准偏差接近n / sqrt(12)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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

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

可以做的是获取一个输出序列，并对照该可能性检查该序列的各种度量。您可以得出一种可信度分数，表明生成算法正在做得很好。

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

但是我们不应该在这里停下来！因为该算法可能会被仅在两个随机播放之间交替的系统欺骗，该随机播放被设计为每个位置的平均准确度为25.5。我们如何做得更好？

我们希望每个位置在不同的洗牌中分布均匀(对于任何给定的纸牌，可能性均等)。因此，在10个改组中，我们可以尝试验证选择是否"看起来一致"。这基本上只是原始问题的简化版本。您可以检查标准偏差看起来是否合理，最小值是否合理以及最大值也是如此。您还可以检查其他值是否有意义，例如最近的两张卡(按我们分配的编号)。

但是我们也不能随便添加这种无穷大的度量，因为如果有足够的统计数据，那么由于某种原因，任何特定的混洗都将不太可能出现(例如，这是极少数混洗中的卡片X，Y，Z出现在其中的一种)订购)。因此，最大的问题是：应该采取哪些正确的测量方法？在这里，我不得不承认我不知道最佳答案。但是，如果您有一个特定的应用程序，则可以选择一组好的属性/度量进行测试，然后使用它们进行测试-这似乎是密码学家处理事物的方式。

关于测试随机性有很多理论。对于卡改组算法的非常简单的测试，您可以进行大量混洗，然后运行卡方检验，以确保每张卡在任何位置翻身的概率都是均匀的。但这不能测试连续的卡是否没有关联，因此您也想对此进行测试。

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

测试随机性的唯一方法是编写一个程序，该程序尝试为被测试的数据建立预测模型，然后使用该模型尝试预测未来的数据，然后证明其预测的不确定性或熵随着时间的流逝趋向于最大化(即均匀分布)。当然，您将始终不确定模型是否已捕获所有必要的上下文。在给定模型的情况下，始终可以构建第二个模型，该模型生成对第一个看起来随机的非随机数据。但是，只要您接受冥王星的轨道对改组算法结果的影响微不足道，那么您应该能够使自己确信其结果是可以接受的随机性。

当然，如果执行此操作，则最好也使用模型来实际创建所需的数据。如果这样做，那么您将回到第一广场。

随机播放许多，然后记录结果(如果即时通讯正确阅读)。我记得看到过"随机数生成器"的比较。他们只是一遍又一遍地测试它，然后绘制结果图。

如果它确实是随机的，则该图将大部分为偶数。

为了进行快速测试，您可以随时尝试对其进行压缩。一旦它不压缩，就可以进行其他测试。

我已经尝试过顽固的尝试，但是它拒绝改组工作。所有测试均失败。它也确实很笨拙，它不会让您指定所需的值范围或类似的内容。

到目前为止还没有代码，因此我将答案中的测试部分复制粘贴到原始问题中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// ...
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随机性是科学的整个分支。

测试52！可能性当然是不可能的。取而代之的是，在3、5和10等较小数量的卡片上尝试随机播放。然后，您可以测试数十亿次随机播放，并使用直方图和卡方统计检验来证明每个排列正好是一个"偶数"数字的时间。

我没有完全关注你的问题。你说

Assume that you have a algorithm that generates randomness. Now how do you test it?

你什么意思？如果您假设可以产生随机性，则无需进行测试。

一旦有了一个好的随机数生成器，就可以轻松地创建一个随机排列(例如，将您的卡片称为1-52。生成52个随机数，依次将每个数字分配给一张卡片，然后根据您的52个随机数进行排序)。您不会通过生成排列来破坏好的RNG的随机性。

困难的问题是您是否可以信任RNG。这是一个示例链接，可让人们在特定环境下讨论该问题。

我自己考虑一下，我会做的事情是这样的：

设置(伪代码)

1
2
3
4
5
6

// 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开始，但是统计能力强于我的人可能会得出更好的数字)。

分析矩阵

如果我们具有完美的随机性，并且可以无限制地执行随机播放，那么对于每张卡和每个位置，该卡在该位置结束的次数与任何其他卡相同。用不同的方式说同一件事：