Amostragem de números pseudoaleatórios
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:
- Amostragem de rejeição para funções de densidade arbitrárias
- Amostragem de transformada inversa para distribuições cujo FDA é conhecido
- Razão de uniformes, combinando uma mudança de variáveis e amostragem de rejeição
- Amostragem de fatias
- Algoritmo Ziggurat, para funções de densidade monotonicamente decrescentes, bem como distribuições unimodais simétricas
- Gerador de números aleatórios de convolução, não é um método de amostragem em si: ele descreve o uso de aritmética em cima de um ou mais métodos de amostragem existentes para gerar distribuições mais envolvidas.
Métodos genéricos para gerar amostras correlacionadas (frequentemente necessários para distribuições de formato incomum ou de alta dimensão):
- Cadeia de Markov Monte Carlo, o princípio geral
- Algoritmo de Metropolis–Hastings
- Amostragem de Gibbs
- Amostragem de fatias
- Cadeia de Markov Monte Carlo de salto reversível, quando o número de dimensões não é fixo (por exemplo, ao estimar um modelo de mistura e estimar simultaneamente o número de componentes da mistura)
- Filtros de partículas, quando os dados observados estão conectados em uma cadeia de Markov e devem ser processados sequencialmente
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]
Ver também
[editar | editar código-fonte]- Distribuição beta#Geração de variáveis aleatórias
- Distribuição de Dirichlet#Geração de variáveis aleatórias
- Distribuição exponencial#Geração de variáveis aleatórias
- Distribuição gama#Geração de variáveis aleatórias
- Distribuição geométrica#Geração de variáveis aleatórias
- Distribuição de Gumbel#Geração de variáveis aleatórias
- Distribuição multinomial#Distribuição de variáveis aleatórias
- Distribuição de Poisson#Geração de variáveis aleatórias
Referências
- ↑ 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.
- ↑ Ripley, Brian D. (1987). Stochastic simulation. Col: Wiley series in probability and mathematical statistics Applied probability and statistics. New York, NY: Wiley
- ↑ 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
- ↑ «Random Number Distributions - GSL 2.7 documentation». The GNU Operating System and the Free Software Movement. Consultado em 18 de agosto de 2022
Bibliografia
[editar | editar código-fonte]- Devroye, L. (1986) Geração de variáveis aleatórias não uniformes . Nova Iorque: Springer
- Fishman, GS (1996) Monte Carlo. Conceitos, Algoritmos e Aplicações . Nova Iorque: Springer
- Hörmann, W.; J Leydold, G Derflinger (2004,2011) Geração automática de variáveis aleatórias não uniformes . Berlim: Springer.
- Knuth, DE (1997) A Arte da Programação de Computadores, Vol. 2 Algoritmos Seminuméricos, Capítulo 3.4.1 (3ª edição).
- Ripley, BD (1987) Simulação Estocástica . Wiley (em português)