Saltar para o conteúdo

Amostragem de números pseudoaleatórios

Origem: Wikipédia, a enciclopédia livre.

A geração de variáveis aleatórias não-uniformes ou amostragem de números pseudoaleatórios é a prática numérica de gerar números pseudoaleatórios que seguem uma determinada distribuição de probabilidade. Os métodos são normalmente baseados na disponibilidade de um gerador PRN uniformemente distribuído . Algoritmos computacionais são então utilizados para manipular uma única variável aleatória, X, ou frequentemente várias, em uma nova variável aleatória Y, de modo que esses valores tenham a distribuição necessária. Os primeiros métodos para simulações de Monte Carlo foram desenvolvidos no projeto Manhattan, publicado por John von Neumann no início da década de 1950.[1]

Distribuições discretas finitas

[editar | editar código-fonte]

Para uma distribuição de probabilidade discreta com um número finito n de índices nos quais a função de massa de probabilidade f assume valores diferentes de zero, o algoritmo de amostragem básico é direto. O intervalo [0, 1) é dividido em n intervalos [0, f(1)), [f(1),f(1) + f(2)), ... A largura do intervalo i é igual à probabilidade f (i). Escolhe-se um número pseudoaleatório uniformemente distribuído X e procura-se o índice i do intervalo correspondente. O então i determinado terá a distribuição f (i).

Formalizar essa ideia se torna mais fácil usando a FDA

É conveniente definir F (0) = 0. Os intervalos n são então simplesmente [ F (0), E (1)), [ E (1), F (2)), ... , [ F ( n − 1), F ( n )). A principal tarefa computacional é então determinar i de modo que F ( i − 1) ≤ X < F (i).

Isso pode ser feito por diferentes algoritmos:

  • Busca linear, custo computacional linear  n.
  • Busca binária, custo de ordem log n .
  • Pesquisa indexada,[2] também conhecida como método de ponto de corte.[3]
  • Método Alias, o tempo computacional é constante, usando algumas tabelas pré-calculadas.
  • Existem outros métodos que tem custo computacional em tempo constante.[3]

Distribuições contínuas

[editar | editar código-fonte]

Métodos genéricos para gerar amostras independentes:

Métodos genéricos para gerar amostras correlacionadas (frequentemente necessários para distribuições de formato incomum ou de alta dimensão):

Para gerar uma distribuição normal :

Para gerar uma distribuição de Poisson :

Bibliotecas de software

[editar | editar código-fonte]

A Biblioteca Científica GNU tem uma seção intitulada "Distribuições de Números Aleatórios" com rotinas para amostragem em mais de vinte distribuições diferentes.[4]

Referências

  1. Von Neumann, John (1951). «Various Techniques Used in Connection with Random Digits». In: Householder, A. S.; Forsythe, G. E.; Germond, H. H. Monte Carlo Methods. Col: National Bureau of Standards Applied Mathematics Series. 12. [S.l.]: US Government Printing Office. pp. 36–38  Also online is a low-quality scan of the original publication.
  2. Ripley, Brian D. (1987). Stochastic simulation. Col: Wiley series in probability and mathematical statistics Applied probability and statistics. New York, NY: Wiley 
  3. a b Fishman, George (9 de março de 2013). Monte Carlo: Concepts, Algorithms, and Applications (em inglês). [S.l.]: Springer Science & Business Media 
  4. «Random Number Distributions - GSL 2.7 documentation». The GNU Operating System and the Free Software Movement. Consultado em 18 de agosto de 2022