c++ - c++ 中的 `rand()` 可以用于生成无偏 bool 值吗？

Question

我写了下面的函数

bool random_bool(double probability)
{
    double p_scaled = probability * (RAND_MAX+1) - rand();
    if ( p_scaled >= 1 ) return true;
    if ( p_scaled <= 0 ) return false;
    return random_bool( p_scaled );
}

假设 rand() 从 {0,1,...,RAND_MAX-1,RAND_MAX} 上的均匀分布生成一个数字，并从后续调用中生成数字对于除密码学之外的所有实际目的都可以被视为独立的，这应该以概率 p 返回 true:两个 if 语句返回 true 的概率略低于 p，false 的概率略高于 1-p，而递归调用处理其他一切。

但是下面的测试失败了:

long long N = 10000000000; //1e10
double p = 10000.0 / N;
int counter = 0;
for (long long i=0;i<N;i++) if (random_bool(p)) counter++;
assert(9672 < counter && counter <= 10330);

assert 语句旨在仅在 0.1% 的情况下失败。然而它总是失败(counter 在 10600 和 10700 之间)。

怎么了？

附注:我看过this问题，但这无济于事......

Answer 1

随机数生成器的一个常见缺陷是略微偏向较小的结果(基本上是在高阶位中略微偏向 0)。当使用简单模组将 RNG 内部状态包装到输出范围时，通常会发生这种情况，除非 RAND_MAX 是内部状态大小的除数，否则它会偏向于高值。这是一个典型的有偏映射实现:

static unsigned int state;

int rand() {
   state = nextState(); /* this actually moves the state from one random value to the next, eg., using a LCG */
   return state % RAND_MAX;  /* biased */
}

偏差的发生是因为较低的值输出并且在状态下有更多的映射。例如，如果状态可以具有值 0-9(10 个值)，并且 RAND_MAX 为 3(因此值为 0-2)，则 % 3 操作的结果取决于状态

Output  State
0       0 3 6 9 
1       1 4 7
2       2 5 8

结果 0 代表过多，因为它有 4/10 的机会被选中，而其他值的概率为 3/10。

作为一个具有更可能值的示例，如果内部 RNG 状态是一个 16 整数，并且 RAND_MAX 是 35767(正如您提到的，它在您的平台上)，那么所有值 [0 ,6000] 将输出 3 个不同的状态值，但剩余的 ~30,000 个值将仅输出 2 个不同的状态值——这是一个很大的偏差。这种偏差往往会导致您的计数器值高于预期(因为 rand() 的返回值小于统一值有利于 p_scaled >= 1 条件。

如果您可以在您的平台上发布 rand() 的确切实现，将会有所帮助。如果结果证明高位有偏差，您可以通过一个好的哈希函数传递从 rand() 获得的值来消除这种情况，但更好的方法可能只是使用高质量的随机源数字，例如 Mersenne Twister .更好的生成器还将具有更大的输出范围(有效，更高的 RAND_MAX)，这意味着您的算法将遭受更少的重试/更少的递归。

即使 Visual Studio 运行时实现存在此缺陷，值得注意的是，这可能至少部分是有意的设计选择 - 使用 RAND_MAX，如 35767，它与状态大小相对质数(通常是 2 的幂), 确保低位更好的随机性，因为 % 操作有效地混合了高位和低位 - 并且具有偏差/非随机低位在实践中通常比高位中的轻微偏差更大的问题，因为rand() 调用者的普遍存在使用 % 缩小范围，这有效地仅使用模数的低阶位，它们是 2 的幂(也很常见)。