使用随机数生成器为随机数生成器池播种

Question

对于一门课程，我正在尝试实施并行 Monte Carlo 模拟。该项目的要求之一是准确的结果应该是可重复的。在我当前的设计中，我有一个工作 'queue' 由 std::default_random_engine 的实例和一组工人实现。一个 worker 获取一个 'job' 并将其用作自己的 rng 的种子（也是 std::default_random_engine 的一个实例）并使用该实例运行模拟。

虽然结果确实是可重复的，但确实给我留下了一些问题：

使用一个 rng 来播种一个 rng 池会产生某种偏见吗？如果这取决于使用哪个 rng（可能确实如此），我应该使用哪个？
这个设计可以吗，还有其他选择吗？

--edit-- 进一步研究后，我注意到以下内容：std::default_random_engine 使用简单的线性同余生成器。它的状态只是它以前的值。这意味着我的 rngs 池的结果完全相同，但移动了一个。 mersenne twister（具有更大的内部状态）没有表现出这种行为：

#include <iostream>
#include <random>

int main(int argc, char** argv)
{
  std::default_random_engine e1(1);
  std::default_random_engine e2(e1());
  std::cout << e1() << ",\n" << e2() << '\n';

  std::mt19937_64 e3(1);
  std::mt19937_64 e4(e1());
  std::cout << e3() << ",\n" << e4() << '\n';
}

输出：

282475249,
282475249
2469588189546311528,
5601807455758261240

Answer 1

Does using a rng to seed a pool of rngs create some kind of bias? If it depends on which rng is used (and it probably does), which one should i use?

有了质量好的 rng（任何新引入的 C++11，但不是旧的 rand()），基本的想法听起来不错，但你不想使用相同的 RNG生成其他 RNG 的种子。原因如下：假设你的 "master" RNG 生成序列 A B C D，你用 A B 和 C D 为其他 RNG 播种：第一个将继续到 B C D...，第二个到 C D 等：基本上每个人都在产生相同的序列，从更远的地方开始。如果你为主人使用不同的 RNG，只有当你的一些 A B C 值在其他 RNG 序列中巧合地靠近在一起时，才会发生这种情况，这样一个 RNG 最终开始重复另一个的序列.一些 C++11 RNG 的周期是如此之大，尽管它们在除了最苛刻的模拟之外几乎不可能发生冲突，并且这种重复不一定那么糟糕 - 取决于模拟。

此外，您可能希望确保相同的种子值不会被使用两次。（当然，您正在重复的任何给定序列可能在统计上并不典型，或者 - 可能同样存在问题 - 可能无法捕捉到非典型的极端情况，但如果你想要可重复性，这是不可避免的。）

Is this design all right...

听起来不错，就像你描述的那样。

Answer 2

视情况而定。一个 PRNG 实际上会生成一个很长的序列基于其内部状态的确定性（非随机）值。如果用于播种的 PRNG 与 PRNG 相关，则它是播种，取决于种子如何初始化内部状态，每个种子生成器都可以轻松地同步生成，最后一个的第一个值是第二个值倒数第二个，以此类推。

实际上，增加每个生成器的种子，而不是使用 PRNG 来获取下一个种子。这应该有效，除非您使用的是 PRNG 也增加（这将是一个非常差的 PRNG）。

正如 PJS 在评论中指出的那样，如果您这样做，将丢弃生成的第一个随机数。一些生成器会使用非常确定性的公式将种子转换为内部状态，并且return生成随机数时基于旧状态的值。

Answer 3

只需使用内部状态向量如此之大的 PRNG，以至于命中重叠序列的风险几乎为零。 MT，内部状态为 2496 字节，当然符合条件。每个种子都带有从 /dev/urandom 或 random.org 等良好硬件源中获取的完整 2496 字节种子，并且出于实际目的，相关几率为零。我不知道你的图书馆是否允许你使用全尺寸的种子，所以如果不允许，找一个可以的。

Answer 4

坦率地说，即使内部状态很大，也没有人能保证序列不会重叠。最重要的是，存在可调试性的问题，这需要问题是可重现的。所以答案是，每个事件都以它自己的稳定（在不同的hardware/node/runs）种子开始。它使结果可重现和可调试。

众所周知的 Monte Carlo 代码 MCNP5+ 很好地使用了这个方案，在多核和 MPI 上运行。要实现它，您需要具有快速向前跳过（a.k.a。蛙跳或丢弃）功能的 RNG。他们中有很多。它们基于快速指数计算，F. Brown 的论文，"Random Number Generation with Arbitrary Stride"，Trans。是。核素。社会。（1994 年 11 月）。基本上，向前跳过是使用 Brown 方法的 log(N)。

这里是最简单的版本，和MCNP5差不多https://github.com/Iwan-Zotow/LCG-PLE63

更复杂（更慢，但质量更高）的 RNG 在这里 http://www.pcg-random.org/

使用随机数生成器为随机数生成器池播种

Seed a pool of random number generators with a random number generator

c++

random

montecarlo