小编Wol*_*ram的帖子

考虑一种算法来测试在特定次数的尝试之后从一组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和Intel Core i5-2500 SandyBridge测试了最新的Xubuntu 12.10,但几年前我在一台较旧的Ubuntu机器上发现了这一点.

我也在Windows 7上使用Unity3D/Mono进行了测试(虽然不确定哪个Mono版本),这里使用System.Random时,X = 55时沟渠发生,而Unity内置的Unity.Random没有可见的沟渠(至少没有)对于X …