random - 寻找在并行 PRNG 中需要 Matsumoto 的 DCMT 算法的演示

Question

在“伪随机数生成器的动态创建”</a>中，Matsumoto 和 Nishimura 告诫不要出于并行模拟的目的粗心地初始化 MT PRNG，因为并行模拟假设来自不同生成器的数字流彼此独立：

并行机器中 PRNG 的通常方案是为每个进程使用一个相同的 PRNG，并使用不同的初始种子。但是，此过程可能会产生不良碰撞，特别是如果生成器基于线性递归，因为在这种情况下，两个伪随机序列的总和满足相同的线性递归，并且可能出现在第三个序列中。如果并行流的数量与状态空间的大小相比变得很大，则危险变得不可忽视。

要成为一个严重的问题，流的数量必须达到多少？在标准 MT MT19937 的情况下，状态空间相当大......我肯定可以看到 20,000 个序列之间存在模 2 ¹⁹⁹³⁷ -1 的线性关系，但是 400 个序列之间的生日悖论式关系怎么样?

看起来这实际上是一个严重的问题，因为并行 PRNG 实现确实包括DCMT，但是如果有一些失败的例子，以及当这成为问题时的一些意义，那就太好了。

Answer 1

这里有一个关于这个问题的讨论。

在 MT 空间中取两条“相距很远”的流，它们的和也满足递归。因此，对第三个流的可能担心不仅仅是 与前两个流的相关性或重叠，而且取决于应用程序，还涉及与前两个流的总和的相关性/重叠。移动到 N 个流，有 O(N**2) 直接和要担心，然后是总和，然后......

仍然不会对我的统计预期寿命造成问题，但我只有 4 个核心 ;-)

所以它比生日悖论更糟糕。这个问题实际上很可能与 log（状态空间的大小）/log(2) 序列有关，对于标准 MT，它大约是 14 个序列。