math - 量化专业随机生成器的非随机性？

Question

我只是读了有关随机数生成器的this interesting question，该生成器从未连续3次生成相同的值。显然，这使随机数生成器不同于标准的统一随机数生成器，但是我不确定如何定量地描述此生成器与不具有此属性的生成器的不同之处。

假设您给了我两个随机数生成器R和S，其中R是一个真正的随机数生成器，而S是一个真正的随机数生成器，其经过修改后永远不会连续生成三次相同的值。如果您没有告诉我哪个是R或S，那么我想想检测出此问题的唯一方法就是运行这些生成器，直到其中三个连续生成相同的值为止。

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

Answer 1

由于Rice's Theorem，因此无法确定哪个是哪个。

证明:令L为正常RNG的输出。令L'为L，但删除所有长度大于等于3的序列。一些TM识别L'，但有些则不能。因此，根据赖斯定理，无法确定TM是否接受L'。

正如其他人指出的那样，您可能可以断言“它已经运行了N步，没有重复三遍”，但是您永远无法跃跃至“它不会重复三位数”。更适当的是，至少存在一台无法确定其是否符合此条件的机器。

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

编辑:辅助证明。假设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)

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