关于Mersenne Twister生成器的周期

Question

我读到梅森旋转发生器具有2¹⁹⁹³⁷ - 1的周期，但我对为什么可能会这样感到困惑。我看到Mersenne Twister算法的这个实现在第一个评论中清楚地说明它生成0到2³²-1范围内的值。因此，在产生2³²-1个不同的随机数之后，它必然会回到起点（种子），因此周期最多可以是2³²-1。

另外（请告诉我是否错误），计算机无法容纳数字（2¹⁹⁹³⁷ - 1）约为4.3×10⁶⁰⁰¹，至少不能在单个存储块中。我在这里错过了什么？

- Daniel Muñoz Parsapoormoghadam

---

MT19937有624字节的状态，所以它可以适应单个块。而你所说的种子包装只适用于线性同余生成器，而MT不是。 - undefined

Answer 1

你的困惑源于认为输出数字和PRNG内部状态必须是一回事。

一些非常老的PRNG（如线性同余发生器）确实会这样做，即将当前输出反馈到生成器中以用于下一步。

然而，包括Mersenne Twister在内的大多数PRNG从一个更大的状态中工作，该状态会被更新并用于生成32位数字（对于本回答的目的来说，这个顺序并不重要）。

事实上，Mersenne Twister确实存储了624个32位值，共19968位，足以包含您所关心的非常长的周期。这些值被单独处理（作为无符号32位整数），而不是作为一个巨大的数字进行单步计算。你从输出中得到的32位随机数与此状态相关，但不能仅凭它自己决定下一个数字。

- Neil Slater

Answer 2

你的观点是错误的

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

下一个生成的随机数可能与已生成的某个数字相同，但是随机数生成器的内部状态将不同。（没有人告诉过你在第 2³² - 1 步时将生成范围 2³² - 1 内的每个数字。）因此，生成的随机数和生成器的内部状态之间不存在双射关系。可以从状态计算生成的随机数，但你甚至不需要这样做。也可以在不生成随机数的情况下步进内部状态。

当然，计算机并不会存储整个数字序列。它是根据内部状态计算出随机数的。考虑像 1，-1，1，-1 ... 这样的数字序列，你可以生成第 N 个数字而无需存储 N 个元素的数字。

- DanielTuzes

---

嗨，谢谢你的回答。不幸的是，我觉得我表达得不够清楚，或者我根本没有理解你的回答。让我用一个非常简单的例子来解释一下。假设我们有以下一组数字：N = {1, 2, 3}，并且我们有一个周期为5的伪随机数生成器（PRNG），也就是说，无论其内部状态如何，它最多可以输出5个不同的数字（这就是我所理解的“周期”）。如果我们将这个PRNG应用于N，那么它如何能够产生5个不同的元素，而N只有3个呢？现在将“3”替换为“2³² - 1”，将“5”替换为“2¹⁹⁹³⁷ - 1”；这是我的真正疑问。 - undefined

或许你是在说MT19937可以有2¹⁹⁹³⁷ - 1个不同的状态（不一定是2¹⁹⁹³⁷ - 1个不同的输出）？那么我就会理解一切了，因为正如你所说的，输出数字与生成器的内部状态之间没有双射关系。 - undefined

@DanielMuñozParsapoormoghadam 我觉得你对“周期”这个概念有些混淆。周期定义了序列何时重复出现，而不是它能产生的“最大不同数字”。所以根据你的例子，使用该伪随机数生成器，它将产生5个数字，每个数字都在集合{1, 2, 3}中，然后会一直重复产生这些相同的5个数字。 - undefined

@DanielMuñozParsapoormoghadam 是的，MT19937可以有那么多个状态。内部状态存储在624个32位字中。624 * 32 = 19968位，其中31位未使用，因此您可以使用19937位。 - undefined