Véletlen számok létrehozása: pzeudovéletlenszám-generátor

A számítógépek determinisztikusak, az általuk végzett műveletek mindig határozott, megjósolható eredményt adnak. Felmerülhet a kérdés, hogy akkor hogyan tudunk vele véletlen folyamatokat modellezni, véletlen számokat létrehozni. Bár számos fizikai folyamat is alkalmas valódi véletlen jelek létrehozására, ezeket pedig digitális számokká alakíthatjuk, e módszer általában túl lassan állítja elő a véletlen számokat ahhoz, hogy szimulációk és mérések számára felhasználhassuk. Éppen ezért az általánosan használt eljárás, hogy algoritmusok segítségével állítunk elő determinisztikus, de véletnennek tűnő számsorozatot. Ezeket az algoritmusokat hívjuk pszeudovéletlenszám-generátornak.

Mivel ezek a generátorok determinisztikusak, meg van az az előnyük, hogy bármikor reprodukálni tudjuk a korábban előállított jelet. Erre a jelgenerátor seed nevű kezdőparaméterét használhatjuk.

Természetesen vannak hátrányai is a pszeudovéletlenszám-generátoroknak. Az egyik, hogy a létrehozott számsornak van egy bizonyos ismétlődési ideje, ennek lejártakor a generátor már pontosan ugyanazt a számsorozatot adja vissza. Ennek oka, hogy a véletlenszám-generátorok meghatározott bitszámon tárolják el belső állapotukat, működésük során pedig előbb utóbb eljutnak egy olyan állapotba, amiben már tartózkodtak valamikor; ezt követően pedig elkezdik ismételni a legenerált számsorozatot. Például egy olyan véletlenszám-generátor ami 16 bit-en tárolja az adatait, legfeljebb 216 létrehozott számsorozatot tud előállítani ismétlés nélkül. Ha segítségével egy olyan zajgenerátort hozunk létre, mely 10 kHz-es mintavételi frekvenciával állít elő fehér zajt, az 6,5 másodperc után már ismétlődni fog, jelentősen korlátozva az alkalmazhatóságát.

A véletlenszám-generátor által létrehozott számsorban, az algoritmustól függően, különböző rövid és hosszú távú kapcsolatok, összefüggések lehetnek. Ezen összefüggések egyes szimulációk során akár hibás eredményre is vezethetnek, amennyiben a véletlenszám-generátor hibája pont torzítja a végeredmény statisztikáját. Ezért fontos, hogy alkalmazás előtt megismerjük véletlenszám-generátorunk tulajdonságait és korlátait.

A véletlenszám-generátorokat számos tesztnek vethetjük alá [1], vizsgálhatjuk a számok eloszlását, az egymás utáni elemek közötti korrelációt, a periódushosszt, a generátor megbízhatóságát jól megfogalmazott és ismert eredményű Monte-Carlo feladatokban. E mellett egy hasznos teszt a spektrálpróba, ahol a legenerált számsorozatból egy térbeli (vagy hipertérbeli ábrát) készítünk, ahol az egymás után legenerált számokból egy-egy pontot ábrázolunk. Ideális esetben ezek a pontok egyenletesen lefednék a teret. Valós esetben a pontok párhuzamos hipersíkokba rendeződnek. Az, hogy hanyadik dimenzióban jelennek meg a hipersíkok, illetve hogy milyen távolság van közöttük, a jelgenerátor típusától és paramétereitől függ. A következő ábrán a Fortran programozási RANDU függvény [2] térbeli eloszlását láthatjuk; már 3 dimenzióban is kialakulnak ezek a síkok. Ez azt jelenti, hogy ha pl. egy szimulációban 3 paramétert szeretnénk egymástól függetlenül változtatni, amennyiben ezzel a függvénnyel hoznánk létre őket, az szimuláció eredménye egyáltalán nem fog megfelelni a valóságnak, hiszen a paraméterek nem lesznek egymástól függetlenek.

A RANDU véletlenszámgenerátor térbeli eredménye

A RANDU véletlenszám-generátor által létrehozott pontok térbeli elhelyezkedése

Olyan pszeudovéletlenszám-generátor nincs, mely minden teszten átmenne, de a legtöbb manapság használt véletlenszám-generátor jól teljesít a tesztek nagy részében, és mindig találhatunk a feladatunkhoz leginkább megfelelő algoritmust.

[1] L’ECUYER, P: Testing random number generators. Proceedings of the 1992 Winter Simulation
Conference, (2002), 305–313. p.

[2] DONALD ERVIN KNUTH: A számítógép-programozás művészete 2. kötet (Szeminumerikus
algoritmusok). Budapest, 1987, Műszaki Könyvkiadó.

Hozzászóllások