尋找並行需要松本DCMT算法的演示PRNG

Question

「Dynamic Creation of Pseudorandom Number Generators」松本和西村警告說，爲了平行仿真的目的，假設來自不同發生器的數字流彼此獨立，MT PRNG的不小心初始化：

並行機器中PRNG的通常方案是對每個進程使用同一個PRNG，並使用不同的初始種子。但是，此過程可能會產生不良碰撞，特別是如果生成器基於線性遞歸，因爲在這種情況下，兩個僞隨機序列的總和滿足相同的線性遞歸，並且可能出現在第三個序列中。如果並行流的數量與狀態空間的大小相比變大，則危險變得不可忽視。

流的數量有多大，這是一個嚴重的問題？在標準MT MT19937的情況下，狀態空間相當大......我可以確定地看到，在20,000個序列中存在線性關係模，但生日 - 悖論式關係之間的關係如何400個序列？

看起來這實際上是一個嚴重的問題，因爲並行PRNG實現包括DCMT，但是有一些失敗的例子，以及某些時候會成爲問題的例子會很好。

Answer 1

有一個關於這個問題的討論here。

在MT空間中取兩條「相距很遠」，其總和也滿足 的復發。因此，關於第三個流的可能擔心不是只是 關於與前兩個流的相關性或重疊，但取決於應用，也取決於與前兩個流的總和 的相關性/重疊。移動到N個流，並有O（N ** 2） 直和擔心，然後款項的總和，並...

仍然不會造成我統計預期壽命的問題，但我 只有4核心;-)

所以它比生日悖論更糟糕。這個問題實際上很可能是log（狀態空間的大小）/ log（2）序列，對於標準MT，這個序列大約是14個序列。