Generació de variants aleatòries no uniformes

Exemple: un registre de desplaçament de 4 bits com a generador pseudoaleatori.

La generació de variables aleatòries no uniformes o el mostreig de nombres pseudoaleatoris és la pràctica numèrica de generar números pseudoaleatoris (PRN) que segueixen una distribució de probabilitat determinada. Els mètodes es basen normalment en la disponibilitat d'un generador PRN distribuït de manera uniforme. Aleshores s'utilitzen algorismes computacionals per manipular una única variable aleatòria, X, o sovint diverses d'aquestes, en una nova variable aleatòria Y de manera que aquests valors tinguin la distribució requerida. Els primers mètodes es van desenvolupar per a les simulacions de Monte-Carlo al projecte Manhattan, publicat per John von Neumann a principis dels anys cinquanta.^[1][2]

Distribucions discretes finites

Per a una distribució de probabilitat discreta amb un nombre finit n d'índexs en què la funció de massa de probabilitat f pren valors diferents de zero, l'algorisme de mostreig bàsic és senzill. L'interval [0,1) es divideix en n intervals [0,f (1)), [f (1),f (1)+f (2)), . . . L'amplada de l'interval i és igual a la probabilitat f (i). Es dibuixa un nombre pseudoaleatori X distribuït uniformement i cerca l'índex i de l'interval corresponent. El tan determinat tindré la distribució f (i).

Formalitzar aquesta idea es fa més fàcil utilitzant la funció de distribució acumulada^[3]

${\displaystyle F(i)=\sum _{j=1}^{i}f(j).}$

És convenient establir F(0) = 0. Els n intervals són llavors simplement [F(0),F(1)), [F(1),F(2)), . . ., [ F(n−1),F(n)). La tasca computacional principal és, aleshores, determinar i per a quin F(i−1)≤X<F(i).

Això es pot fer mitjançant diferents algorismes:

• Cerca lineal, temps computacional lineal en n.
• Cerca binària, el temps de càlcul va amb registre n.
• Cerca indexada, també anomenada mètode de punt de tall.
• Mètode d'àlies, el temps de càlcul és constant, utilitzant algunes taules precalculades.
• Hi ha altres mètodes que costen temps constant.^[4]

Distribucions contínues

Mètodes genèrics per generar mostres independents:

• Mostreig de rebuig per a funcions de densitat arbitràries.
• Mostreig de transformada inversa per a distribucions el CDF de les quals es coneix.
• Ratio d'uniformes, combinant un canvi de variables i un mostreig de rebuig.
• Mostra de rodanxes.
• Algorisme zigurat, per a funcions de densitat decreixents monòtonament així com distribucions unimodals simètriques.
• Generador de números aleatoris de convolució, no un mètode de mostreig en si mateix: descriu l'ús de l'aritmètica a sobre d'un o més mètodes de mostreig existents per generar distribucions més implicades.

Referències

1. «NON-UNIFORM RANDOM VARIATE GENERATION» (en anglès). http://luc.devroye.org.+[Consulta: 19 juny 2023].
2. L’Ecuyer, Pierre. Non-uniform Random Variate Generations (en anglès). Berlin, Heidelberg: Springer, 2011, p. 991–995. DOI 10.1007/978-3-642-04898-2_408. ISBN 978-3-642-04898-2. 
3. Morgan, B. J. T.; Devroye, L. «Non-Uniform Random Variate Generation.». Non-Uniform Random Variate Generation, 44, 9-1988, pàg. 919. DOI: 10.2307/2531615.
4. «Non-Uniform Random Variate Generation» (en anglès). http://luc.devroye.org.+[Consulta: 19 juny 2023].