Pszeudo-véletlen számok mintája

Az álvéletlen számok mintavételezése egy adott valószínűségi eloszlás szerint elosztott pszeudovéletlen számok  generálásának gyakorlata . Numerikus módszerek alapján .

A nem egyenletes eloszláson alapuló mintavételi módszerek jellemzően egy pszeudo-véletlen számgenerátor azon képességét használják ki, hogy X számot generáljanak , amelyek egyenletes eloszlásúak . Ezután egy számítási algoritmust alkalmazunk, amely az X valószínűségi változóval végzett manipulációk eredményeként egy Y valószínűségi változót ad vissza , amelynek értékei kielégítik az adott eloszlást.

Véges diszkrét eloszlások

Egy véges számú n valószínűségi változó értékkel rendelkező diszkrét eloszláshoz , amelyben az f valószínűségi függvény nullától eltérő értékeket vesz fel, az alapvető mintavételi algoritmus meglehetősen egyszerű. A [0, 1) intervallum n intervallumra van felosztva [0, f (1)), [ f (1), f (1) + f (2)), … Az i intervallum hossza egyenlő a valószínűséggel f ( i ). Tegyük fel, hogy valaki kap egy egyenletes eloszlású X számot , amelyhez a megfelelő intervallum i indexét rendeljük. Az így meghatározott i indexnek f ( i ) eloszlása ​​lesz .

Az elmondottakat könnyű formalizálni a (halmozott) eloszlásfüggvénnyel

Célszerű beállítani F (0) = 0. Ekkor n intervallum a következő alakú lesz: [ F (0), F (1)), [ F (1), F (2)), …, [ F ( n − 1), F ( n )). És ekkor a fő számítási feladat olyan i keresése lesz , amelyre F ( i − 1) ≤ X < F ( i ).

A keresés többféle algoritmussal is végrehajtható, például:

• Lineáris keresés lineáris számítási bonyolultsággal.
• Bináris keresés logaritmikus összetettséggel.
• És más típusú keresések.

Folyamatos terjesztések

A független minták előállításának általános módszerei :

• Minta eltéréssel tetszőleges sűrűségfüggvényekhez.
• Inverz transzformációs módszer , ha az eloszlásfüggvény ismert
• Mintavétel szintek szerint
• Ziggurat algoritmus monotonan csökkenő sűrűségű függvényekhez, valamint szimmetrikus unimodális eloszláshoz

Általános módszerek korrelált minták generálására (gyakran szükséges például többváltozós eloszlások esetén):

• Markov lánc Monte Carlo módszerek , alapelv
• Metropolis-Hastings algoritmus
• Gibbs mintavétel
• Mintavétel szintek szerint
• Monte Carlo átmenetek fordított algoritmusa a Markov-lánc séma szerint, ha a dimenzió nem rögzített
• Többrészecskeszűrő , amikor a megfigyelt adatok Markov-láncba kapcsolódnak, és szekvenciálisan kell feldolgozni

A normál eloszlás szerinti generáláshoz :

• Box-Muller transzformáció
• Marsaglia poláris módszer

Szoftverkönyvtárak

A GNU Tudományos Könyvtárban van egy "Véletlenszámú eloszlás" című rész, amely több mint húsz különböző eloszlás szerinti mintavételi eljárást tartalmaz. [egy]

Jegyzetek

1. ↑ GNU Tudományos Könyvtár - Kézikönyv: Véletlenszámú elosztások . www.gnu.org. Letöltve: 2018. január 5. Az eredetiből archiválva : 2018. január 9.. (határozatlan)

Irodalom

• Devroye, L. (1986) Non-Uniform Random Variate Generation. New York: Springer

• Fishman, G. S. (1996) Monte Carlo. Fogalmak, algoritmusok és alkalmazások. New York: Springer
• Hörmann, W.; J Leydold, G Derflinger (2004,2011) Automatic Nonuniform Random Variate Generation. Berlin: Springer
• Knuth, D.E. (1997) A számítógép-programozás művészete , 1. évf. 2 Félnumerikus algoritmusok , 3.4.1. fejezet (3. kiadás)
• Ripley, B. D. (1987): Sztochasztikus szimuláció . Wiley