c - libc 随机数生成器有缺陷？

Question

考虑一种算法来测试在特定次数的尝试后从一组 N 个唯一数字中选出某个数字的概率(例如，当 N=2 时，轮盘赌(没有 0)的概率是多少X 试图让黑方获胜？)。

正确的分布是 pow(1-1/N,X-1)*(1/N)。

但是，当我使用以下代码对此进行测试时，在 X=31 处总是有一条深沟，与 N 无关，也与种子无关。

这是由于使用中的 PRNG 的实现细节而无法避免的固有缺陷，这是一个真正的错误，还是我忽略了一些明显的东西？

// C

#include <sys/times.h>
#include <math.h>
#include <stdio.h>

int array[101];
void main(){

    int nsamples=10000000;
    double breakVal,diffVal;
    int i,cnt;

    // seed, but doesn't change anything
    struct tms time;
    srandom(times(&time));

    // sample
    for(i=0;i<nsamples;i++){
        cnt=1;
        do{
            if((random()%36)==0) // break if 0 is chosen
                break;
            cnt++;
        }while(cnt<100);
        array[cnt]++;
    }

    // show distribution
    for(i=1;i<100;i++){
        breakVal=array[i]/(double)nsamples; // normalize
        diffVal=breakVal-pow(1-1/36.,i-1)*1/36.; // difference to expected value
        printf("%d %.12g %.12g\n",i,breakVal,diffVal);
    }
}

在带有 libc6 包 2.15-0ubuntu20 和英特尔酷睿 i5-2500 SandyBridge 的最新 Xubuntu 12.10 上进行了测试，但几年前我已经在一台旧的 Ubuntu 机器上发现了这一点。

我还在 Windows 7 上使用 Unity3D/Mono 测试了这个(虽然不确定是哪个 Mono 版本)，这里当使用 System.Random 时沟渠发生在 X=55，而 Unity 的内置 Unity.Random 没有可见的沟渠(至少不是 X<100)。

分布:

差异:

Answer 1

这是由于 glibc 的 random()功能不够随机。根据this page , 对于 random() 返回的随机数，我们有:

o<sub>i</sub> = (o<sub>i-3</sub> + o<sub>i-31</sub>) % 2^31

或:

o<sub>i</sub> = (o<sub>i-3</sub> + o<sub>i-31</sub> + 1) % 2^31 .

现在取x<sub>i</sub> = o<sub>i</sub> % 36 ，并假设上面的第一个等式是使用的(每个数字都有 50% 的几率发生这种情况)。现在如果x<sub>i-31</sub>=0和 x<sub>i-3</sub>!=0 ，那么 x<sub>i</sub>=0 的机会小于 1/36。这是因为 50% 的时间 o<sub>i-31</sub> + o<sub>i-3</sub>将小于 2^31，当发生这种情况时，

x<sub>i</sub> = o<sub>i</sub> % 36 = (o<sub>i-3</sub> + o<sub>i-31</sub>) % 36 = o<sub>i-3</sub> % 36 = x<sub>i-3</sub> ,

这是非零的。这会导致您在 0 个样本之后看到 31 个样本。