量化专门的随机生成器的非随机性？

Question

我刚刚在this interesting question上读到一个随机数生成器，它永远不会连续三次生成相同的值。这显然使随机数生成器不同于标准的均匀随机数生成器，但我不确定如何定量描述此生成器与没有此属性的生成器的不同。

假设您交给我两个随机数生成器，R和S，其中R是一个真正的随机数生成器，S是一个真正的随机数生成器，它已经被修改为永远不会连续三次产生相同的值。如果你没有告诉我哪一个是R或S，我能想到的唯一方法就是运行生成器，直到其中一个连续三次产生相同的值。

我的问题是--有没有更好的算法来区分这两个生成器？除了阻止三个相同的值连续出现之外，不产生三次相同数字的限制是否会以某种方式影响生成器的可观察行为？

Answer 1

作为Rice's Theorem的结果，没有办法区分哪个是哪个。

证明:设L是正常RNG的输出。设L‘为L，但去掉了所有长度为>= 3的序列。有些TM能识别L'，但有些不能。因此，根据赖斯定理，判断TM是否接受L‘是不可判定的。

正如其他人所指出的，您可能能够做出这样的断言：“它已经运行了N个步骤而没有重复三次”，但您永远不能跳到“它永远不会重复一个数字三次”。更恰当地说，至少存在一台您无法确定其是否满足此标准的计算机。

警告:如果你有一个真正的随机生成器(例如核衰变)，那么莱斯的定理可能不适用。我的直觉是，这个定理仍然适用于这些机器，但我从未听人讨论过它。

EDIT：第二次校样。假设P(X)以高概率确定X是否接受L'。我们可以构造一个(无限数量的)程序F，如下所示：

F(x): if x(F), then don't accept L'
      else, accept L'

P不能确定F(P)的行为。此外，假设P正确地预测了G的行为。我们可以构造：

F'(x): if x(F'), then don't accept L'
       else, run G(x)

因此，对于每一个好的案例，都必须至少存在一个坏案例。

Answer 2

如果S是通过拒绝R来定义的，那么S产生的序列将是R产生的序列的子序列。例如，取一个简单的随机变量X，其为1或0的概率相等，您将得到：

R = 0 1 1 0 0 0 1 0 1
S = 0 1 1 0 0 1 0 1

区分这两者的唯一真正方法是寻找条纹。如果你正在生成二进制数，那么条纹是非常常见的(如此之多，以至于人们几乎总是可以区分随机的100位序列和学生试图随机写下的序列)。如果这些数字是从[0,1]中统一获取的，那么条纹就不太常见了。

这是一个简单的概率练习，一旦知道了分布，就可以计算三个连续数字相等的概率，或者更好地计算所需的预期数字数量，直到三个连续数字相等的概率大于您最喜欢的p的p。

Answer 3

由于您定义了它们只是在特定属性方面有所不同，因此没有更好的算法来区分这两者。

当然，如果您对随机值进行三元组，则生成器S将比R更频繁地生成所有其他三元组，以补偿丢失的三元组(X,X,X)。但是要得到一个有意义的结果，你需要更多的数据，而不是第一次连续三次找到任何值的成本。