Рассмотрим алгоритм проверки вероятности того, что определенное число выбрано из набора из 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);
}
}
Протестировано на обновленном Xubuntu 12.10 с пакетом libc6 2.15-0ubuntu20 и Intel Core i5-2500 SandyBridge, но я обнаружил это уже несколько лет назад на более старой машине Ubuntu.
Я также тестировал это на Windows 7, используя Unity3D/Mono (не уверен, какая версия Mono, хотя), и здесь канава происходит при X = 55 при использовании System.Random, в то время как Unity встроил Unity.Random не имеет видимой канавы ( по меньшей мере, не для X < 100).
Распределение: 
Различия: 
