random - 关于 Mersenne Twister 发电机的时期

Question

我读过 Mersenne Twister 发电机的周期为 2¹⁹⁹³⁷ - 1，但我很困惑为什么这可能。我看到了 Mersenne Twister 算法的这种实现，在第一条评论中它清楚地说它产生的值在 0 到 2³² - 1 的范围内。因此，在它产生 2³² - 1 个不同的随机数之后，它必然会回到起点（种子），因此周期最大为 2³² - 1。

另外（如果我错了，请告诉我），至少在一个内存块中，计算机不能保存数字 (2¹⁹⁹³⁷ - 1) ~ 4.3×10⁶⁰⁰¹。我在这里想念什么？

Answer 1

您的困惑源于认为 PRNG 的输出编号和内部状态必须是同一件事。

一些非常古老的 PRNG 曾经这样做过，例如 Linear Congruental Generators。在这些发生器中，电流输出被反馈到发生器中以进行下一步。

但是，包括 Mersenne Twister 在内的大多数 PRNGS 都从一个更大的状态工作，它会更新并使用它来生成一个 32 位数字（就本答案而言，执行的顺序并不重要）。

事实上，Mersenne Twister 确实存储了 624 乘以 32 位的值，也就是 19968 位，足以包含您想知道的很长一段时间。这些值单独处理（作为无符号 32 位整数），在单步计算中不被视为一个巨大的数字。您从输出中获得的 32 位随机数与此状态相关，但本身并不能确定下一个数字。

Answer 2

你错了

因此，在它产生了 2³² - 1 个不同的随机数之后，它必然会回到起点（种子）...

没错，下一个数字可以与已经生成的数字中的一个相同，但是随机数生成器的内部状态不会相同。（没有人告诉你，2³² - 1 范围内的每个数字都将在第 2³² - 1 步生成。）所以生成的随机数和生成器的内部状态之间没有双射。生成的随机数可以从状态中计算出来，但您甚至不必这样做。您也可以在不创建随机数的情况下步进内部状态。

当然，计算机不会存储整个数字序列。它从内部状态计算随机数。考虑一个像 1, -1, 1, -1 ... 这样的数字序列，您可以在不存储 N 个元素的情况下生成第 N 个数字。