为什么人们说在使用随机数发生器时存在模数偏差？
我曾经看到过很多这个问题，但从来没有见过这个问题的具体答案。 所以我打算在这里发布一个，希望能够帮助人们理解为什么在使用随机数生成器时为什么会出现“模偏差”，如C ++中的rand() 。
所以rand()是一个伪随机数发生器，它选择一个介于0和RAND_MAX之间的自然数， RAND_MAX是一个在cstdlib定义的常量（请参阅本文以获取关于rand()的一般概述）。
现在如果你想在0和2之间生成一个随机数，会发生什么？ 为了说明起见，假设RAND_MAX是10，我决定通过调用rand()%3来生成一个介于0和2之间的随机数。 但是， rand()%3不会以相等的概率产生0到2之间的数字！
当rand()返回rand()或9时， rand()%3 == 0 。 因此，P（0）= 4/11
当rand()返回rand()或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参考
永远Confuzzled
保持选择随机是消除偏见的好方法。
更新
如果我们搜索一个可被n整除的x，我们可以使代码更快。
// Assumptions
// rand() in [0, RAND_MAX]
// n in (0, RAND_MAX]
int x = rand();
// Keep searching for an x in a range divisible by n
while (x >= RAND_MAX - (RAND_MAX % n)) {
x = rand();
}
x %= n;
上面的循环应该非常快，平均说1次迭代。
@ user1413793对于这个问题是正确的。 我不打算进一步讨论，除了要说一点：是的，对于小的n值和RAND_MAX大值，模数偏差可能非常小。 但是使用偏差诱导模式意味着每次计算随机数时必须考虑偏差，并针对不同情况选择不同的模式。 如果你做出错误的选择，它引入的错误是微妙的，单元测试几乎是不可能的。 与只使用适当的工具（比如arc4random_uniform ）相比，这是额外的工作，而不是更少的工作。 做更多的工作并获得更糟的解决方案是糟糕的工程，特别是在大多数平台上，每次都很容易。
不幸的是，解决方案的实现都不正确或效率低于他们应该。 （每个解决方案都有各种解释问题的注释，但没有一个解决方案已经解决了这些问题。）这可能会让偶然的答案搜索者感到困惑，所以我在这里提供了一个已知好的实现。
同样，最好的解决方案就是在提供它的平台上使用arc4random_uniform ，或者为您的平台使用类似的范围解决方案（例如Java上的Random.nextInt ）。 它将为您做任何正确的事情，而无需代码费用。 这几乎总是正确的要求。
如果你没有arc4random_uniform ，那么你可以使用opensource的力量来查看它是如何在更宽范围的RNG之上实现的（在这种情况下是ar4random ，但类似的方法也可以在其他RNG上运行） 。
这是OpenBSD的实现：
/*
* Calculate a uniformly distributed random number less than upper_bound
* avoiding "modulo bias".
*
* Uniformity is achieved by generating new random numbers until the one
* returned is outside the range [0, 2**32 % upper_bound). This
* guarantees the selected random number will be inside
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
* after reduction modulo upper_bound.
*/
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
u_int32_t r, min;
if (upper_bound < 2)
return 0;
/* 2**32 % x == (2**32 - x) % x */
min = -upper_bound % upper_bound;
/*
* This could theoretically loop forever but each retry has
* p > 0.5 (worst case, usually far better) of selecting a
* number inside the range we need, so it should rarely need
* to re-roll.
*/
for (;;) {
r = arc4random();
if (r >= min)
break;
}
return r % upper_bound;
}
值得注意的是，对于那些需要实现类似事情的人来说，这个代码的最新提交评论是：
更改arc4random_uniform（）以计算2**32 % upper_bound'' as -upper_bound％upper_bound''。 简化代码并使其在ILP32和LP64体系结构上保持不变，并且在LP64体系结构上使用32位余数而不是64位余数稍快一些。
由Jorden Verwer在tech @ ok deraadt指出; 没有djm或otto的反对意见
Java实现也很容易找到（请参阅上一个链接）：
public int nextInt(int n) {
if (n <= 0)
throw new IllegalArgumentException("n must be positive");
if ((n & -n) == n) // i.e., n is a power of 2
return (int)((n * (long)next(31)) >> 31);
int bits, val;
do {
bits = next(31);
val = bits % n;
} while (bits - val + (n-1) < 0);
return val;
}
上一篇: Why do people say there is modulo bias when using a random number generator?