量化随机性

Question

我想出了两种生成相对较短的随机字符串的方法——其中一种更快更简单，另一种更慢但我认为更随机。有没有一种不太复杂的方法或方式来衡量每种方法产生的数据有多随机呢？

我尝试压缩输出字符串（通过zlib）来确定数据越真正随机，压缩得就越少，但这并没有证明太多。

- tMC

---

如果您所问的是统计随机性，那么有一些测量方法。 - martineau

随机性（在一般意义上）实际上是方法的属性，而不是其输出的属性。因此，如果您描述这两种方法，您将获得更有用的反馈。 - David Z

Answer 1

你正在使用标准压缩作为无法计算的科尔莫戈洛夫复杂度的代理，这是量化随机性的“正确”数学框架（但不幸的是，它是无法计算的）。

如果你愿意假设某种字符串分布，你也可以尝试一些熵度量。

- ely

Answer 2

您可以使用一些映射将字符串转换为数字，然后应用标准测试，如Diehard和TestU01。请注意，需要长序列的样本（通常几MB的文件即可）。

- Nishanth

Answer 3

如果一个结果无法提前确定，那么它被认为是随机的。如果可以确定，那么它被认为是确定性的。这是一个二元分类，结果要么是确定性的，要么是随机的，没有随机程度。然而，可预测性有不同的程度。可预测性的一种度量是熵，正如EMS所提到的。

考虑两个游戏。在任何给定的玩法中，你都不知道自己会赢还是输。在游戏1中，获胜的概率是1/2，也就是说，在长期内你大约有一半的时间会赢。在游戏2中，获胜的几率是1/100。两个游戏都被认为是随机的，因为结果并不是绝对确定的。游戏1的熵比游戏2高，因为结果更不可预测——虽然有赢的机会，但你很可能在任何一次尝试中输掉。

通过一种好的压缩算法，可以实现对一系列值的压缩量与序列的熵有关。英语的熵相当低（字母的相对频率和出现为组的单词序列中有很多冗余信息），因此往往可以很好地压缩。

- pjs