可以用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}数字,后续调用中的数字可以被视为独立于除加密之外的所有实际目的,这应该true以概率返回p:两个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);

断言语句仅在0.1%的情况下失败.但它始终失败(counter介于10600和10700之间).

怎么了？

PS:我看过这个问题,但没有帮助......

Answer 1

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

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 */
}

之所以会出现偏差，是因为较低的值输出在状态 mod 下有更多的映射。例如，如果状态可以具有值 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 运行时实现存在此缺陷，值得注意的是，它可能至少部分是有意的设计选择 - 使用像 35767 这样与状态大小互质的 RAND_MAX（通常是 2 的幂），确保较低位的随机性更好，因为 % 操作有效地混合了高位和低位 - 并且在实践中，具有偏置/非随机低位位通常比高位中的轻微偏差更大的问题，因为它无处不在使用 % 缩小范围的调用者的方法rand()，它仅有效地使用 2 的幂的模数的低位（也很常见）。