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.

Distribuições discretas finitas

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

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

É 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, também conhecida como método de ponto de corte.
• Método Alias, o tempo computacional é constante, usando algumas tabelas pré-calculadas.
• Existem outros métodos que tem custo computacional em tempo constante.

Distribuições contínuas

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 :

• Transformada de Box-Muller
• Método polar de Marsaglia

Para gerar uma distribuição de Poisson :

• Veja Distribuição de Poisson#Gerando variáveis aleatórias distribuídas por Poisson

Bibliotecas de software

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.

Ver também

• 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

Bibliografia

• 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)