寻找对松本DCMT算法并行PRNG需求的演示



在"动态创建伪随机数生成器" Matsumoto 和 Nishimura 告诫不要为了并行模拟而粗心地初始化 MT PRNG,这些模拟假设来自不同生成器的数字流彼此独立:

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

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

看起来这实际上是一个严重的问题,因为并行 PRNG 实现确实包括 DCMT,但最好有一些失败的例子,并且对于这成为问题时有一些意义。

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

取 MT 空间中"相距很远"的两个流,它们的总和也满足 复发。 因此,对第三流的担忧不仅仅是 关于与前两个流的相关性或重叠,但是, 取决于应用程序,也与 前两个流。 移动到 N 个流,并且有 O(N**2) 直接的金额要担心,然后是总和,然后...

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

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

最新更新