Egyedi eloszlású véletlenszámok

Lesz olyan pont az életedben, amikor nem egyenletes eloszlású, vagy nem normális eloszlású véletlenszámokra lesz szükséged. Tegyük most fel, hogy élelmet kereső véletlen bolyongó vagy. észszerű élelemkereső stratégiának tűnik véletlenszerűen vándorolni a térben. Végül is nem tudod, hol van az ennivaló, akár keresheted véletlenszerűen is, amíg meg nem találod. Ahogy már valószínűleg te is rájöttél, a probléma az, hogy a véletlen bolyongó többször is visszatér azokra a helyekre, ahol korábban már járt (ezt „túlmintavételezésnek” hívják). Az ilyen problémák elkerülésére az egyik lehetséges stratégia az, ha időnként egy nagyon nagy lépést teszünk. Ezáltal a bolyongó egy ideig véletlenszerűen járkál egy körzetben, majd időnként jó messzire ugrik, hogy lecsökkentse a túlmintavételezést. A véletlen bolyongás ilyen módosítása (amit Lévy-repülésnek hívnak) saját valószínűséghalmazt igényel. Bár ez nem a Lévy-repülés pontos megvalósítása, a valószínűségeloszlást meghatározhatjuk így is: minél hosszabb a lépés, annál kisebb a valószínűsége, hogy ugyanoda kerüljön, minél rövidebb a lépés, annál nagyobb.

Ennek a fejezetnek egy korábbi részében láttuk, hogyan csinálhatunk saját valószínűségeloszlást úgy, hogy egy tömböt feltöltünk értékekkel (egyes értékek ismétlődnek, hogy megnöveljük kiválasztásuk valószínűségét), vagy amikor teszteltük a random() függvény eredményét. Úgy implementáljuk a Lévy-repülést, hogy azt mondjuk, annak a valószínűsége, hogy a bolyongó nagyot lép, kisebb, mint 1%.

var r = random(1);
// 1%-os valószínűséggel lép nagyot a bolyongó
if (r < 0.01) {
  xstep = random(-100, 100);
  ystep = random(-100, 100);
} else {
  xstep = random(-1, 1);
  ystep = random(-1, 1);
}

Viszont ez a megoldás a választási valószínűséget korlátozott számú lehetőségre csökkenti le. Mi van akkor, ha ennél általánosabb szabályt szeretnénk, például annál nagyobb valószínűséggel válasszunk ki egy számot, minél magasabb az értéke? 3,145-et nagyobb valószínűséggel válasszuk ki, mint 3,144-et, még akkor is, ha a különbség nagyon kicsi. Más szóval, ha x egy véletlenszám, a valószínűségét az y tengelyen az y = x függvénnyel ábrázolhatjuk.

Ha rájövünk, hogy hogyan kell a fenti grafikonnak megfelelő véletlen eloszlást generálni, akkor ugyanazt a módszert alkalmazhatjuk bármilyen görbére, aminek ismerjük a képletét.

Az egyik megoldás az, hogy egy helyett két véletlenszámot választunk. Az első véletlenszám marad az, ami: egy véletlenszám. A másodikat „felhasználhatóságot szabályozó véletlenszámnak” fogjuk hívni. Ez azt fogja nekünk megmondani, hogy használjuk-e az első számot, vagy eldobjuk azt, és új számot válasszunk helyette. Azokat a számokat, amik könnyebben megfelelnek a felhasználhatósági kritériumnak, gyakrabban fogjuk kiválasztani, míg azokat, amik ritkán felelnek meg, ritkábban választjuk. Kövessük az alábbi lépéseket (most csak a 0 és 1 közötti véletlenszámokra szorítkozunk):

Válassz ki egy véletlenszámot: R1.
Számold ki a P valószínűséget, ami az R1 érvényesítési kritériuma lesz. Legyen most P = R1.
Válassz ki egy másik véletlenszámot: R2.
Ha R2 kisebb, mint P, akkor megtaláltuk a számunkat—R1!
Ha R2 nem kisebb, mint P, kezdd előröl az 1. lépéssel.

Itt azt mondjuk, hogy annak a valószínűsége, hogy egy véletlenszám felhasználható, megegyezik a véletlenszám értékével. Tegyük fel, hogy az R1 0,1 lett. Ez azt jelenti, hogy 10%-os esélye van arra, hogy felhasználjuk. Ha R1 értéke 0,83, akkor 83%-os esélye van arra, hogy fel fogjuk használni. Minél nagyobb a szám, annál nagyobb a valószínűsége, hogy felhasználjuk.

Itt egy függvény (nevét a Monte Carlo módszerről kapta, amit a Monte Carlo kaszinóról neveztek el), ami a fenti algoritmust valósítja meg. A függvény 0 és 1 közötti véletlenszámokat ad vissza. Ez a program a visszaadott értékeket ellipszisek méretezésére használja, de ezeket az értékeket bármi másra is fel lehetne használni. (A programban található megjegyzések és szövegek: 1. sor: Dan Shiffman, natureofcode.com példája alapján; 3. sor: Véletlenszámokat generáló függvény, mely a magas értékeket előnyben részesíti. Nevét a Monte Carlo módszerről kapta; 7. sor: Ez a rész a „végtelenségig” fut: mindaddig, amíg nem találunk felhasználható értéket; 9. sor: Válassz ki egy véletlenszámot!; 11. sor: Rendelj hozzá egy valószínűséget!; 13. sor: Válassz egy második véletlenszámot!; 15. sor: Felhasználható? Ha igen, akkor megvagyunk; 22. sor: Generálj 10 véletlenszámot, ami alapján ellipsziseket hozol létre!)

Ez a „Természetes szimulációk" tananyag a Daniel Shiffman által készített „The Nature of Code” alapján készült, a Creative Commons Attribution-NonCommercial 3.0 Unported License szerint.

Szeretnél részt venni a beszélgetésben?

Jelentkezz be

Rendezés:

Még nincs hozzászólás.

Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.