random - PRNG 中有多少个州（比如 Mersenne Twister），下一个州的分布是什么？

Question

对于像 Mersenne Twister 这样的周期为 2^19937-1 的 PRNG，PRNG 是否有那么多状态？即，由于PRNG没有更多的状态可以进入，所以状态开始重复？

作为跟进，假设您存在于 PRNG 的某个当前状态，下一个状态的分布是什么？我正在运行长时间的模拟，并有兴趣找出使用随机种子的一个模拟何时可能会进入另一个使用不同随机种子的模拟中存在的状态。

Answer 1

伪随机数生成器 (PRNG) 的工作原理是将确定性函数应用于当前状态以确定下一个状态，然后将该状态投影到返回位数上。询问“如果您以当前状态退出，下一个状态的分布是什么”基本上没有意义。由于转换是确定性的，因此从任何给定的状态来看，只有一个状态将成为下一个状态。最终，您将不可避免地回到某个先前观察到的状态，从那时起，这些状态及其相应的输出投影将以相同的顺序重复，我们说您的 PRNG 已经循环。循环长度取决于从您的起点（种子状态）可以达到多少个独特状态，并且受限于但不一定等于状态空间的大小。例如，有些函数仅在以偶数为种子时才产生偶数，或在以奇数为种子时才产生奇数。在重复之前，这些情况都不会产生所有可能的整数。

Mersenne Twister通过具有 19937 位的状态空间实现了 2 ¹⁹⁹³⁷ -1的周期长度。（如果我没记错的话，-1 是因为从任何其他非零状态都无法到达全 0 的状态。）至于两次运行中重叠状态的可能性，忘记它。为了让您了解 2 ¹⁹⁹³⁷ -1 有多大，请考虑以下内容：物理学家估计已知宇宙中大约有 10 ⁸⁰ = 2 ²⁶⁶个亚原子粒子。如果您使用完整状态初始化（例如通过从/dev/random字节缓冲区读取 2.5KB）独立播种运行，即使您使用的是 10 ¹⁰你问的随机数相当于你在 2 个^19937-300宇宙中两次选择同一个亚原子粒子的可能性有多大。它只是不会发生。