Keskustelu: Yleinen keskustelu: Onko randomissasi jotain vikaa?

Olen tutkinut erilaisia random-funktioita ja todennut, että kun printin ottaa vaikka 10000000 sämppelin välein, 0 tahi 1 eivät ole samanarvoisia. Random funktio painottaa joko nollaa tai ykköstä, kun siitä otetaan modulo kaksi. Testaappa oma randomisi.

Tosin ahkeran tutkimisen ja kokeilemisen myötä onnistuin kehittämään randomin, joka ei painota kumpaakaan - enää. Kun randomista otetaan modulo kaksi ja kasvatetaan sen mukaan taulukon nolla tai ykkös alkiota, niin printti 10000000 askelin välein on yhä yhtä kaaosta ja arvo pomppii ykkösen ja nollan ympärillä, niin kuin pitääkin.

Jos oma randomisi tai valmis-randomi tekee tämän, niin onnittelut!

Sinänsä voi olla että kehittämäsi randomi on huonompi kuin se alkuperäinen parillisia tai parittomia painottava, vaikka tuossa asiassa näyttääkin paremmalta.

Huvikseni testasin .Net Frameworkin vakio Random-luokalla (joka on pseudo-random), ja se ei painottanut kuvaamallasi tavalla.

Kuulostaa hyvältä. Oliko muuten mainisi triviaali:

void main(void)
{
   unsigned C[2]={0, 0};
   unsigned cou=0;
   for (;;)
   {
      ++C[rnd()%2];
      if (++cou==10000000)
      {
         printf("%d", C[0]>C[1]? 1: 0);
         cou=0;
      }
   }
}

Ja jos randomi näyttää hyvältä, voi kokeilla "toisen kertaluvun" ilmentymää.

void main(void)
{
   unsigned C[2]={0, 0};
   unsigned X[2]={0, 0};
   unsigned cou=0;
   for (;;)
   {
      ++C[sun_rnd()%2];
      if (++cou==10000000)
      {
         ++X[C[0]>C[1]? 1: 0];
         printf("%d", X[0]>X[1]? 1: 0);
         cou=0;
      }
   }
}

Jos sun_rnd on hyvä, kaaoksen pitäisi näkyä myös tässä testissä.

Esimerkiksi php:n funktio rand() palauttaa parittomia ja parillisia lukuja "täysin sattumanvaraisesti" vaikkei se ole kovinkaan satunnainen. Tämän huomaa jo siitä, että visualisoimalla tulokset kohinakuvan muotoon, siitä erottuu selvää säännönmukaisuutta. (Tosin en voi olla varma, että rand() toimisi omalla koneellani identtisesti tuon hyvin vanhan kuvan generointiin käytetyn version kanssa.)

Kannattaa kuitenkin aivan ensiksi varmistaa itselleen, että osaa analysoida satunnaisuutta ennen kuin lähtee kehittämään viallisten testimetodien kautta "parempia" algoritmeja.

Kryptografisessa mielessä tällä todistelulla ei liene mitään painoarvoa, mutta jos ajatellaan luvut bittijonoina, niin parittomuuden tutkiminen kertoo ainoastaan viimeisestä bitistä. Jos luvussa on 16, 32 tai jopa 64 bittiä, niin loppujen 15-63 bitin laatuun se ei ota kantaa laisinkaan. Lisäksi pelkästään lukumääriä laskiessa ongelmana on se, että esimerkiksi sarja 11111000001111100000 näyttää nollien ja ykkösten määrissä satunnaiselta muttei toistuessaan sitä ole.

Sitä en ymmärrä, miksi koet, että vain joka 10. miljoonannen luvun tarkastelu antaa paremman arvion. Äkkiseltään luulisi, että virhemarginaalia jää 10 miljoonaa kertaa enemmän.

rand(),

Randomin säännönmukaisuus, johtuu siintä että niillä voi turvallisesti ja luottaen tehdä esim. peliin, metsää taikka peltoa taikka jokia.

Jos olisi täysin randomi, niin, ajoittain olisi keskittymä möykkyjä jossain osin ruutua kun tekee random metsää esim. laudalle.

Koti tietokoneen random on säännönmukainen, jotta, sitä voi käyttää sellaisenaan, eikä joudu tekemään tarkistuksia, esim. kun tekee metsän laudalle, kuten minun pelissäni, en joudu koskaan tarkistamaan että onko tilanne 1 mahdollisuus 10 000, esim. että kaikki puut olisivatkin laudan yläreunassa, täyden satunnaisuuden mukaan.

Kotitietokoneitten random on aloittelijoille tarkoitettu, täyden satunnaisuuden kanssa, joutuisi aloittelija tehdä liikaa tarkistuksia. :)

Minulla on tulossa pelejä joissa parannan tietokoneen randomia, minä lasken keskiarvoja ja jaan tulevia nopan heittoja, niin, että keskiarvo heitoissa, on molemmilla jonkin tietyn minimi ja maksimi ero rajan sisään.

Mutta, kotitietokoneitten random on niin hyvä pelaamiseen yleisesti, että, en joudu valittamaan kokemuksiani peli suunnittelun kanssa, se on säännönmukainen, mutta, estää siten nämä älyttömät möykky tulokset, kuten siis aloittelijan puitten sijainti laudalla.

:)

--

JoinTuanJanohon kirjoitti:

Random funktio painottaa joko nollaa tai ykköstä, kun siitä otetaan modulo kaksi.

Oletko testannut juurikaan muita kuin LCG-tyyppisiä tai viallisia generaattoreita? Maailmassa on tusinoittain algoritmeja, joilla saadaan niin hyviä satunnaislukuja, että sinun kotikutoiset testisi eivät löydä niistä vikaa.

JoinTuanJanohon kirjoitti:

Tosin ahkeran tutkimisen ja kokeilemisen myötä onnistuin kehittämään randomin,

Oletko testannut randomiasi millään oikeilla tilastollisilla testeillä? Kohtuullisena lähtökohtana voi pitää vaikka Diehard-testejä, vaikka toki niistäkin voi päästä läpi aika huonolla generaattorilla. Lisätietoa on myös sivustolla random.org.

The Alchemist kirjoitti:

Tosin en voi olla varma, että [PHP:n] rand() toimisi omalla koneellani identtisesti tuon hyvin vanhan kuvan generointiin käytetyn version kanssa.

PHP:n versiosta 7.1 alkaen rand on ollut itse asiassa sama kuin mt_rand (käsittääkseni juuri satunnaislukujen laadun parantamiseksi).

HannuTapio kirjoitti:

Randomin säännönmukaisuus, johtuu siintä että niillä voi turvallisesti ja luottaen tehdä esim. peliin, metsää taikka peltoa taikka jokia.

Huonolla satunnaislukugeneraattorilla kartasta voi tulla tylsä, koska puut voivat tulla esimerkiksi suoriin riveihin tai jonkin muun säännöllisen kuvion mukaan. Hyvän kartan saa, kun käyttää hyviä satunnaislukuja ja tarvittaessa lisää generointiin ehtoja, esimerkiksi jonkin rajan, paljonko puita pitää olla ja miten lähekkäin ne saavat olla.

Eihän se ykkösten ja nollien esiintymismäärä mistää satunnaislukugeneraattorin toiminnasta kerro. Jos molempien todennäköisyys on 50 %, odotusarvon perusteella niitä olisi yhtä paljon. Kuitenkin kun jokaisen tapauksen pitäisi olla itsenäinen, on pieni mahdollisuus että kaikki olisivat vain toista arvoa.

Jos arvot rajattomasti arvoja niin tulos lähetyy 50-50-tilannetta. Jos aina ja jokaisella (parillisella) arvontamäärällä molempien osuus on yhtä suuri, täytyy generaattorin pitää muistissa vanhat arvot, jolloin uuden luvun generointi ei ole enää satunnaista: siihen vaikuttaa onko niitä tähän asti arvottu enemmän vai vähemmän kuin sitä toista lukua.

Toisaalta jos jakauma olisi tasainen jokaisella arvontojen määrällä, ei se enää olisi edes satunnaislukugeneraattori. Se vain palauttaisi niitä vuorotellen...

Metabolix kirjoitti:

Oletko testannut randomiasi millään oikeilla tilastollisilla testeillä? Kohtuullisena lähtökohtana voi pitää vaikka Diehard-testejä, vaikka toki niistäkin voi päästä läpi aika huonolla generaattorilla. Lisätietoa on myös sivustolla random.org.

Miksi pitäisi soveltaa jotain analyysejä, jos random ei läpäise yksinkertaisinta ajateltavissa olevaa testiä?

void main(void)
{
   unsigned C[2]={0, 0};
   unsigned cou=0;
   for (;;)
   {
      ++C[sun_rnd()%2];
      if (++cou==10000000)
      {
         printf("%d", C[0]>C[1]? 1: 0);
         cou=0;
      }
   }
}

JoinTuanJanohon kirjoitti:

Miksi pitäisi soveltaa jotain analyysejä, jos random ei läpäise yksinkertaisinta ajateltavissa olevaa testiä?

Oli kyse sinun randomistasi: Oletko testannut itse kehittämääsi randomia (joka läpäisee tuon oman testisi) millään yleisesti käytetyillä muilla testeillä?

JoinTuanJanohon kirjoitti:

Miksi pitäisi soveltaa jotain analyysejä, jos random ei läpäise yksinkertaisinta ajateltavissa olevaa testiä?

Siksi, että ”jotkin analyysit” antavat todellista tietoa ja ”yksinkertaisin ajateltavissa oleva testi” on ilmeisesti väärin ajateltu.

Tuossa koodissasi ei ole mitään selvää testiä. Oletan kuitenkin, että testisi tarkoitus on katsoa, että nollien ja ykkösten välinen suhde on jatkuvasti (alusta nykyiseen kohtaan) noin 1:1. Silloin testaat aivan väärää asiaa. Sinun pitäisi printtauksen yhteydessä nollata myös laskuri (koodissasi C) ja tarkistaa siis, että suhde N-kokoisessa satunnaisotoksessa on yhtä usein yli kuin alle 1:1. Syy on seuraava:

Otetaan esimerkiksi aito satunnainen tapahtuma eli kolikonheitto. Jos ensin on heitetty oikeasti sattumalta 1000 kertaa kruuna ja 0 kertaa klaava, miten jatkossa tapahtuu? Sinun testisi mukaan seuraavien 1000 heiton pitäisi olla pelkkää klaavaa, jotta saataisiin suhde takaisin keskelle (1000:1000). Tämä on selvästi väärä tavoite. Hyvässä satunnaisuudessa aikaisempi tulos ei saa vaikuttaa seuraavaan todennäköisyyteen. Seuraavan 1000 heiton joukossa ”pitäisi” siis olla kaikesta huolimatta noin 500 kruunaa ja 500 klaavaa, ja edellisten 1000 heiton tuloksesta riippumatta pitäisi olla yhtä todennäköistä saada enemmän kruunaa tai enemmän klaavaa.

Vai luuletko, että tuhannen väärän lottorivin jälkeen olet jo vähän lähempänä päävoittoa?

Testissäsi on myös sellainen epätasapaino, että arvot parillisen määrän lukuja mutta et huomioi tasatulosta. Testisi kannalta ”täydellinen” satunnaisfunktio, joka arpoo tasan yhtä monta nollaa ja ykköstä, ei läpäise testiäsi, koska lukumäärät ovat aina yhtäsuuret ja siis koodisi tulostaa pelkkiä nollia. Jos haluat välttää tasapelit, arvo pariton määrä lukuja.

Heitän vielä kiusallani seuraavan funktion, joka näköjään tuurilla läpäisee testisi (jos ymmärsin testin sisällön oikein). En kehdannut edes katsoa, millaisia lukuja tämä tuottaa, mutta ei varmaan kovin hyviä. :D

int sun_rnd() {
   static unsigned x, y;
   ++x; ++y;
   return (((x * 3 + 5) + (y * 7 + 11)) >> 8) & 0xffff;
}

Edit: Katsoin sittenkin, ja tuli näköjään maailman paras satunnaisfunktio, nimittäin monotonisesti kasvava, kunnes pyörähtää ympäri. Todellakin tuurilla läpäisee testin.

Metabolix kirjoitti:

...nollata myös laskuri...

Ok.