3

考虑以下输入：

1,1,2,3,5,8- 这不是随机的

2,4,8,16,32- 这既不是

4,1,2,11,5,9- 这个看起来像随机序列

我想问一下是否有这样的算法来证明输入是随机的还是不是？

4

3 回答 3

5

不，没有这样的证明——如果你有完全随机数，每个长度为 n 的序列的概率是相等的。但是，有一些统计测试可以评估随机数生成器的质量，这可能是您正在寻找的。请参阅顽固测试。

于 2013-01-14T15:45:05.263 回答
1

正如其他人所提到的，您无法证明序列是否是随机生成的。除了@timos建议的内容之外，您似乎还有一些额外的要求。似乎您希望确保该序列不是来自一些众所周知的“非随机”序列的假设列表。如果是这种情况，您可能有兴趣学习在线整数序列百科全书。

如果您有特定的顺序，您可以对照他们的数据库进行检查。例如，1,1,2,3,5,8出现在许多序列中，但最突出的是A000045（斐波那契数）。类似的序列4,1,2,11,5,9不会出现在那里的搜索中。

这些都不能证明任何事情，但也许这更符合您在这种情况下的目标。

于 2013-01-14T16:44:39.757 回答
0

我想在这里强调一下，“随机”这个词不仅意味着同分布，而且独立于其他一切（包括独立于任何其他选择）。

有许多可用的“随机性测试”，包括通过运行各种统计探针估计p 值的测试，以及估计min-entropy的测试，这大致是位序列的最小“可压缩性”水平和最相关的熵衡量“安全随机数生成器”。还有各种“随机性提取器”，例如冯诺依曼和佩雷斯提取器，它们可以让您了解可以从位序列中提取多少“随机性”。然而，所有这些测试和方法只能在随机性定义的第一部分（“均匀分布”）上比在第二部分（“独立”）上更可靠。

通常，没有算法可以仅从数字序列中判断该过程是否以独立且同分布的方式生成它们，而不知道该过程是什么。因此，例如，尽管您可以判断给定的位序列中的零多于一，或者其中没有明显的模式，但您无法判断这些位是否——</p>

  • 真正独立于任何其他选择而生成，或
  • 构成仅“局部随机”的极长周期序列的一部分，或
  • 只是从另一个进程中重用，或者
  • 以其他方式产生的，

...没有有关该过程的更多信息。作为一个重要的例子，一个人选择密码的过程在这个意义上很少是“随机的”，因为密码往往包含熟悉的单词或名称，以及其他原因。

另请参阅此问题：A Good and SIMPLE Measure of Randomness

于 2020-12-07T12:13:58.977 回答