我想出了两种方法来生成相对较短的随机字符串——一种更快更简单，另一种更慢，但我认为更随机。是否有一种不太复杂的方法或方法来测量每种方法的数据可能有多随机？
我已经尝试压缩输出字符串（通过 zlib），确定数据越真正随机，压缩的越少，但这并没有证明太多。
问问题
716 次
3 回答
9
您正在使用标准压缩作为不可计算的Kolmogorov Complexity的代理，这是量化随机性的“正确”数学框架（但不幸的是，不可计算）。
如果您愿意假设某种分布在字符串上，您也可以尝试一些熵测量。
于 2013-05-01T14:52:16.200 回答
0
如果无法提前确定地预测结果，则认为结果是随机的。如果可以确定地预测，则认为它是确定性的。这是一个二元分类，结果要么是确定性的，要么是随机的，没有随机性的程度。然而，有一定程度的可预测性。正如 EMS 所提到的，可预测性的一种度量是熵。
考虑两个游戏。你不知道在任何给定的比赛中你会赢还是输。在第 1 场比赛中，获胜的概率是 1/2，即从长远来看，您赢了大约一半的时间。在第二场比赛中，获胜的几率是 1/100。这两场比赛都被认为是随机的，因为结果不是绝对确定的。第 1 场比赛的熵比第 2 场比赛更大，因为结果更难以预测——虽然有获胜的机会，但你很确定在任何给定的试验中你都会输。
值序列（通过良好的压缩算法）可以实现的压缩量与序列的熵有关。英语的熵非常低（在字母的相对频率和作为组出现的单词序列中都有很多冗余信息），因此往往压缩得很好。
于 2013-05-02T00:51:11.533 回答
0
您可以使用一些映射将字符串转换为数字，然后应用标准测试，例如Diehard和TestU01。请注意，需要长序列的样本（通常只需几个 MB 文件即可）
于 2013-05-01T14:58:36.393 回答