Keskustelu: Yleinen keskustelu: Satunnaislukujen laatu

void main(void)
{
   unsigned bit[2]={0, 0};
   int status=0;
   for (;;)
   {
      unsigned P=rnd();
      ++bit[(unsigned)(P%2)];
      if (status==0 && bit[1]>bit[0])
      {
         printf("%d", bit[0]>bit[1]? 1: 0);
         status=1;
      }
      if (status==1 && bit[0]>bit[1])
      {
         printf("%d", bit[0]>bit[1]? 1: 0);
         status=0;
      }
   }
}

Jos pseudo-random tuottaa tasaisen jakauman, voi olettaa, että tila esimerkiksi bittien 0 ja 1 välillä muuttuu loputtomasti.

Eli siis jaksolla n1 ykkösiä on enemmän kuin nollia.
Sen jälkeen tila muuttuu, ja jaksolla n2 nollia on enemmän kuin ykkösiä.

Jos tila jämähtää ykköseen tai nollaan, rnd-funktion jakauma ei ole tasainen.

Hyvän pseudo-randomin pitäisi vielä tuottaa tasainen jakauma graafisestikin, eikä olla jollain attaktorilla.

Olet pahasti hakoteillä.

Purkkaviritelmien sijaan kannattaa perehtyä tilastoihin ja katsoa vaikka NISTin testipatteria tai hieman vanhempia Diehard-testejä. Lisätietoa on myös sivustolla random.org.

Tekemäsi yksinkertainen testi ei tuota todellista tietoa satunnaisuudesta. Testin voi läpäistä tuottamalla toistuvasti esimerkiksi luvut 123, 124, 124, 125. Näyttääkö tämä mielestäsi satunnaiselta?

// Tämä funktio läpäisee aloittajan antaman testin.
int rnd() {
	static unsigned i;
	int j[] = {123, 124, 124, 125};
	return j[i++ % 4];
}

Hyvän satunnaisuuden ei edes kuulu läpäistä tuota testiä. Testisi perusteella on nimittäin niin, että mitä enemmän nollia kertyy, sitä varmemmin seuraavana tulee jo ykkönen. Tällainen ennakkotieto seuraavasta luvusta on satunnaisuuden vastaista.

Jos heität kolikkoa 100 kertaa ja tulos 30–70, onko kolikossa vikaa? Jos heität toiset 100 kertaa, pitääkö tuloksen nyt olla 70–30 vastapainoksi? Jos heität kolikolla 100 kertaa kruunan, onko seuraava heitto todennäköisemmin kruuna vai klaava?

Samasta asiasta on keskusteltu aikaisemmin. Oletko jopa sama henkilö?

Sen vuoksi sanoinkin, että: "Hyvän pseudo-randomin pitäisi vielä tuottaa tasainen jakauma graafisestikin, eikä olla jollain attaktorilla." - tai toistaa jotain numerosarjaa.

Ellei pseudo-random läpäise testiäni, se on huono.

jone2712 kirjoitti:

Ellei pseudo-random läpäise testiäni, se on huono.

Itse olen pikemminkin sitä mieltä, että jos (pseudo-)random säännönmukaisesti läpäisee testisi, se on huono.

jone2712 kirjoitti:

Sen vuoksi sanoinkin, että: "Hyvän pseudo-randomin pitäisi vielä tuottaa tasainen jakauma graafisestikin, eikä olla jollain attaktorilla." - tai toistaa jotain numerosarjaa.

Pseudosatunnaislukugeneraattori (PRNG) nimenomaan toistaa jotain sarjaa. Jokaisella PRNG:llä on jokin rajallisen suuruinen tila. Jos tila on esimerkiksi 32-bittinen, se voi toistaa (enintään) 4294967296 luvun sarjaa. Monet algoritmit käyttävät paljon suurempaa tilaa, mutta johtopäätös on sama: joskus alkaa toisto.

jone2712 kirjoitti:

Ellei pseudo-random läpäise testiäni, se on huono.

Mikä tahansa PRNG epäonnistuu testissäsi, jos testaaminen aloitetaan sopivasta tilasta. Syy tähän on selvä: Jossain kohdassa nollien määrä on suurimmillaan. Jos testaaminen aloitetaan tuosta kohdasta, ei tule ikinä hetkeä, jolloin nollia olisi kertynyt enemmän, vaan parhaimmillaankin päästään vain siihen, että nollia ja ykkösiä on sama määrä, ja kaikilla muilla hetkillä ykkösiä on enemmän.

Tämän tapauksen voi demonstroida muuttamalla edellisessä esimerkissäni lukusarjan aloituskohtaa:

// Tämä funktio ei enää läpäise aloittajan antamaa testiä.
int rnd() {
	static unsigned i = 3;
	int j[] = {124, 124, 125, 123};
	return j[i++ % 4];
}

Samanlainen aloituskohta löytyy mille tahansa periodiselle PRNG:lle. (Ne ovat kaikki periodisia, koska tila on rajallinen ja siksi väistämättä toistuu lopulta.)

Itse asiassa lievä epätasapaino sinun testissäsi ei edes ole kriittinen ongelma, jos generaattorin tila on erittäin suuri. Esimerkiksi Mersenne Twisterin periodin pituus on 2^19937-1, eli tasapelistä puuttuu yksi luku. Kuitenkin vaikka kaikki maailman tietokoneet arpoisivat eri siemenluvuista Mersenne Twisterillä maapallon tuhoon asti, kaikkia lukuja ei ehdittäisi käydä läpi eli kukaan ei huomaisi tuota puuttuvaa lukua.

Monissa kielissä onkin valittu perinteisen LCG:n (a*b+c) tilalle juuri Mersenne Twister, joka pärjää keskimäärin kohtuullisen hyvin erilaisissa testeissä, vaikka siinäkin on kyllä omat puutteensa.