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

Question

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

Answer 1

所以 rand() 是一个伪随机数生成器，它选择一个介于 0 和 RAND_MAX 之间的自然数，它是 cstdlib 中定义的常量code>(参见 article 了解 rand() 的一般概述)。

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

当 rand() 返回 0、3、6 或 9 时， rand()%3 == 0。因此，P(0) = 4/11

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

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

这不会以相等的概率生成 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() 执行 RAND_MAX/n 调用。

更有效的公式方法是取一些长度可被 n 整除的大范围，例如 RAND_MAX - RAND_MAX % n，不断生成随机数，直到得到一个在范围内，然后取模数:

int x;

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

x %= n;

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

---

作品引用和延伸阅读:

• CPlusPlus Reference

• Eternally Confuzzled

---