C++ uniform_int_distribution 总是在第一次调用时返回 min()

Question

在标准库的至少一个实现中，第一次调用 std::uniform_int_distribution<> 不返回随机值，而是返回分布的最小值。也就是说，给定代码:

default_random_engine engine( any_seed() );
uniform_int_distribution< int > distribution( smaller, larger );
auto x = distribution( engine );
assert( x == smaller );

... x实际上会是 smaller对于 any_seed() 的任何值, smaller , 或 larger .

要在家一起玩，您可以尝试 code sample在 gcc 4.8.1 中演示了这个问题。

我相信这是不正确的行为？如果这是正确的行为，为什么随机分布会返回这个明显非随机的值？

Answer 1

对观察到的行为的解释

这就是uniform_int_distribution如果可能结果的范围小于 rng 产生的数字范围，则将随机位映射到数字:

const __uctype __uerange = __urange + 1; // __urange can be zero
const __uctype __scaling = __urngrange / __uerange;
const __uctype __past = __uerange * __scaling;
do
  __ret = __uctype(__urng()) - __urngmin;
while (__ret >= __past);
__ret /= __scaling;

哪里__urange是larger - smaller和 __urngrange是 rng 可以返回的最大值和最小值之间的差值。 (代码来自 libstdc++ 6.1 中的 bits/uniform_int_dist.h)

在我们的例子中，rng default_random_engine是 minstd_rand0 , 产生 __scaling == 195225785对于您测试的 [0,10] 范围。因此，如果 rng() < 195225785 ，分布将返回 0。

第一个数字a minstd_rand0返回是

(16807 * seed) % 2147483647

(其中 seed == 0 被调整为 1 顺便说一句)。因此我们可以看到 minstd_rand0 产生的第一个值用小于 11615 的数字播种将产生 0 与 uniform_int_distribution< int > distribution( 0, 10 );你用过。 (修改我的错误。;))

您提到了较大种子会消失的问题:一旦种子变得足够大以实际使 mod 操作执行某些操作，我们就不能简单地将整个范围的值按除法分配给相同的输出，因此结果将看起来更好。

这是否意味着(libstdc++ 的) 被破坏了？

没有。您总是选择较小的随机 32 位种子，从而引入了明显的偏差。结果中出现的这种偏见并不令人惊讶或邪恶。对于随机种子，即使是你的 minstd_rand0将产生一个相当均匀随机的第一个值。 (尽管之后的数字序列的统计质量不高。)

对此我们能做些什么？

情况1:您想要统计质量高的随机数。

为此，您可以使用更好的 rng，例如 mt19937并播种其整个状态空间。对于 Mersenne Twister，这是 624 个 32 位整数。 (作为引用，here 是我尝试通过答案中的一些有用建议正确地做到这一点。)

情况 2:您确实只想使用那些小种子。

我们仍然可以从中得到不错的结果。问题是伪随机数生成器通常“有点持续”地依赖于它们的种子。为了解决这个问题，我们丢弃了足够多的数字，让最初相似的输出序列发散。所以如果你的种子必须很小，你可以像这样初始化你的 rng:

std::mt19937 rng(smallSeed);
rng.discard(700000);

为此使用像 Mersenne Twister 这样好的 rng 是至关重要的。我不知道有什么方法可以从播种不良的种子中获得体面的值(value) minstd_rand0 ，例如参见 this train-wreck .即使播种得当，mt19937 的统计特性远远优于。

您有时会听到的对大状态空间或缓慢生成的担忧在嵌入式世界之外通常是无关紧要的。根据boost和 cacert.at , MT 甚至比 minstd_rand0 快得多.

虽然您的结果肉眼看起来不错，但您仍然需要使用丢弃技巧。在我的系统上用时不到一毫秒，而且您不会经常播种 rng，所以没有理由不这样做。

请注意，我无法准确估计我们需要的丢弃物数量，我从 this answer 中获取了该值, 它链接 this paper为理性。我现在没有时间解决这个问题。