为什么人们说使用随机数生成器时存在模偏差？

Question

我看到这个问题被问了很多，但从未见过真正具体的答案。因此，我将在这里发布一篇文章，希望能帮助人们理解为什么在使用随机数生成器（如 C++ 中的 rand() ）时究竟存在“模偏差”。

原文由 user1413793 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

所以 rand() 是一个伪随机数生成器，它在 0 和 RAND_MAX 之间选择一个自然数，这是在 cstdlib 中定义的常数（参见这篇 文章 rand() 的一般概述。

现在如果你想生成一个介于 0 和 2 之间的随机数会发生什么？为了解释起见，假设 RAND_MAX 是 10，我决定通过调用 rand()%3 来生成 0 到 2 之间的随机数。但是， rand()%3 不会以相同的概率产生 0 和 2 之间的数字！

当 rand() 返回 0、3、6 或 9 时， rand()%3 == 0 。因此，P(0) = ⁴⁄₁₁

当 rand() 返回 1、4、7 或 10 时， rand()%3 == 1 。因此，P(1) = ⁴⁄₁₁

当 rand() 返回 2、5 或 8 时， rand()%3 == 2 。因此，P(2) = ³⁄₁₁

这不会以相等的概率生成 0 和 2 之间的数字。当然，对于较小的范围，这可能不是最大的问题，但对于较大的范围，这可能会扭曲分布，使较小的数字产生偏差。

那么 rand()%n 什么时候以相等的概率返回从 0 到 n-1 的数字范围？当 RAND_MAX%n == n - 1 。在这种情况下，连同我们之前的假设 rand() 确实以相等的概率返回一个介于 0 和 RAND_MAX 之间的数字，n 的模类也将均匀分布。

那么我们如何解决这个问题呢？一种粗略的方法是不断生成随机数，直到获得所需范围内的数字：

 int x;
do {
    x = rand();
} while (x >= n);

但这对于 n 的低值是低效的，因为您只有 n/RAND_MAX 获得范围内值的机会，因此您需要执行 RAND_MAX/n 平均调用 rand() 。

一种更有效的公式方法是采用一些长度可被 n 整除的大范围，例如 RAND_MAX - RAND_MAX % n ，继续生成随机数，直到得到一个位于该范围内的随机数，然后取模数：

 int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

对于 n 的小值，这很少需要多次调用 rand() 。

---

作品引用和延伸阅读：

• CPlusPlus 参考

• 永远的困惑

---

原文由 user1413793 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

模减少是使随机整数生成器避免永远运行的最坏情况的常用方法。

然而，当可能的整数范围未知时，通常没有办法在不引入偏差的情况下“修复”这种永远运行的最坏情况。这不仅仅是模减少（ rand() % n ，在接受的答案中讨论）会以这种方式引入偏差，还有 Daniel Lemire 的“乘法和移位”减少，或者如果你在之后停止拒绝结果一组迭代次数。 （要清楚，这并不意味着没有办法解决伪随机生成器中存在的偏差问题。例如，即使模数和其他归约通常是有偏差的，如果可能的范围内，它们不会有偏差问题整数是 2 的幂 ， 如果随机生成器产生无偏随机位或它们的块。）

该答案的其余部分将显示随机生成器中运行时间和偏差之间的关系。从这里开始，我们将假设我们有一个“真正的”随机生成器，它可以产生无偏且独立的随机位。*

1976 年，DE Knuth 和 AC Yao 表明，任何仅使用随机位以给定概率生成随机整数的算法都可以表示为二叉树，其中随机位指示遍历树和每个叶子（端点）的方式对应一个结果。在这种情况下，我们正在处理在 [0, n) 中生成随机整数的算法，其中每个整数的选择概率为 1/n。如果对于所有结果，树中出现相同数量的叶子，则该算法是 无偏 的。但是，如果 1/n 具有非终止二进制展开式（如果 n 不是 2 的幂，则会出现这种情况），则该算法只有在以下情况下才会无偏：

• 二叉树具有“无限”深度，或
• 二叉树最后包括“拒绝”叶子，

在任何一种情况下，算法都不会在恒定时间内运行，并且在最坏的情况下会永远运行。 （另一方面，当 n 是 2 的幂时，最优二叉树将具有有限深度且没有拒绝节点。）

二叉树的概念还表明，任何“修复”这种最坏情况时间复杂度的方法通常都会导致偏差。 （同样，这并不意味着没有办法解决伪随机生成器中存在的偏差问题。）例如，模约简相当于一棵二叉树，其中拒绝叶被标记的结果替换——但因为有更多可能结果比拒绝叶子，只有一些结果可以代替拒绝叶子，从而引入偏见。如果您在一定次数的迭代后停止拒绝，则会产生相同类型的二叉树 - 以及相同类型的偏差。 （但是，根据应用程序，这种偏差可能可以忽略不计。随机整数生成也有安全方面的问题，在这个答案中讨论太复杂了。）

为了说明，以下 JavaScript 代码实现了 J. Lumbroso (2013) 称为 快速骰子滚轮 的随机整数算法。请注意，它包括一个拒绝事件和一个循环，这是使算法在一般情况下无偏见所必需的。

 function randomInt(minInclusive, maxExclusive) {
 var maxInclusive = (maxExclusive - minInclusive) - 1
 var x = 1
 var y = 0
 while(true) {
    x = x * 2
    var randomBit = (Math.random() < 0.5 ? 0 : 1)
    y = y * 2 + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1
    }
 }
}

笔记

\* 此答案不涉及 C 中的 rand() 函数，因为它 有很多问题。也许这里最严重的事实是，C 标准没有明确指定 rand() 返回的数字的特定分布，甚至没有统一分布。

原文由 Peter O. 发布，翻译遵循 CC BY-SA 4.0 许可协议