Rascunhos sobre geração de números aleatórios

Edição de 08h56min de 27 de outubro de 2010

Aline

Referência:

PERIN FILHO, Clovis. Introdução à Simulação de Sistemas. Editora da Unicamp, Campinas, 1995

Geração de variáveis aleatórias

Para se realizar simulações é necessário utilizar sequências de variáveis aleatórias. Para obter tais sequências, é possível utilizar três métodos:

• Uso de sequências de observaçoes efetuadas previamente;
• Uso de sequências geradas aleatoriamente a partir de distribuições empíricas construídas a partir de observações efetuadas previamente;
• Uso de sequências geradas aleatoriamente a partir de distribuições clássicas cujos parâmetros foram estimados de acordo com observações efetuadas previamente.

A primeira alternativa torna-se inviável em uma simulação de sistemas por ser um processo demorado e que exige muita memória.

Para a segunda e terceira alternativas é necessário usar um gerador de números aleatórios, ferramenta que permite obter valores de variáveis aleatórias com a distribuição desejada.

Muitos dos geradores de números aleatórios são baseados em eventos físicos, utilizando equipamentos simples, tasi como roletas, ou complexos, como dispositivos eletrônicos ou radioativos. Porém, estes geradores raramente são utilizados em uma simulação de sistema, por serem 'lentos, dispendiosos e de difícil implementação'.

Utiliza-se normalmente rotinas computacionais em simulação, sendo divididas em duas fases: a primeira na qual são gerados números aleatórios com distribuição uniforme, e a segunda na qual tais números são transformados em um valor da variável desejada.

No entanto, estes números gerados computacionalmente são denominados pseudo-aleatórios, por serem gerados de 'modo determinístico a partir de uma semente, necessária para iniciar o processo de geração de números aleatórios por computador.'

Muitas vezes, a semente é um número inteiro formado por uma parte dos bits do registrador do relógio interno do computador. É possível dizer que as variáveis geradas se comportam como se fossem verdadeiramente aleatórias.

Números aleatórios

Um gerador de números aleatórios gera uma sequência de números inteiros e uma sequência de números reais a partir de uma semente inteira. Os números inteiros gerados são referente à ordem em que foram gerados.

Ana

Os números pseudo-aleatórios utilizados pelo método de Monte Carlo são usados para determinar atributos (como energia, direção de escape, etc.) de uma partícula lançada e interações da partícula com o meio. Analisando essa situação, as seguintes propriedades de números pseudo-aleatórios são desejáveis:

• As seqüências de números pseudo-aleatórios não devem ser correlacionadas.

• O gerador utilizado deve ser capaz de produzir seqüências durante um longo período sem repetição.

• A seqüência gerada deve ser uniforme e imparcial.

• O gerador deve ser eficiente

Gerador Linear-Congruente

<math> x_{n+1} = (Ax_n + C) (mod\ M) </math>

O numero inteiro aleatório <math>x_{n+1}</math> é gerado a partir do número aleatório anterior, <math>x_n</math> , das constantes inteiras A e C e do módulo inteiro M. Depois que o inteiro <math>Ax_n + C</math> é gerado, o módulo aritmético é realizado a partir do módulo M para produzir o novo inteiro aleatório <math>x_{n+1}</math> . Para começar, o algoritmo requer uma semente inicial <math>x_0</math>, que deve ser fornecida através de algum meio. Uma característica desse tipo de gerador é que o próximo número aleatório <math>x_{n+1}</math> depende exclusivamente do inteiro antecessor, <math>x_n</math> , o que minimiza a necessidade de armazenamento, mas isso impõe algumas restições no período. Com <math>x_n</math> determinado, é possível gerar um número real correspondente da seguinte forma:

<math>R_n = \frac{x_n}{float(M)}</math> (para valores distribuídos no intervalo [0,1))

<math>R_n = \frac{x_n}{float(M-1)}</math> (para valores distribuídos no intervalo [0,1])

O método mais comum para se gerar números pseudo-aleatórios usa uma técnica recursiva chamada gerador linear-congruente, ou gerador de Lehmer. A seqüência é definida numa coleção de inteiros através da fórmula de recursão:

<math> x_{n+1} = (Ax_n + C) (mod\ M) </math>

Onde: xn = é o enésimo membro da seqüência A, C, M = são parâmetros que podem ser ajustados por conveniência e para assegurar a natureza pseudo-aleatória da seqüência. Por exemplo: M, o módulo, é freqüentemente o tamanho de uma palavra no computador e A, o multiplicador, é escolhido para produzir um longo período de seqüência e boas propriedades estatísticas. Exemplo prático: x0 = 13, A = 21, C = 1, M = 32 Seqüência produzida: 13, 18, 24, 25, 14, 7, 20, 5, 10...

Referência:

WARNOCK, Tony. Random-Number Generators. Los Alamos Science, Los Alamos, no. 15, p. 125-130, 1987. Disponível em: < http://library.lanl.gov/cgi-bin/getfile?15-12.pdf >. Acesso em: 05 set. 2010.

Verdadeiros números aleatórios podem ser gerados somente por dispositivos eletrônicos mas como os modelos de simulação são executados em computadores, isso torna-se inviável por ser lento para esse propósito. Outra desvantagem é que as etapas de depuração, verificação e validação dos modelos de simulação, às vezes, exigem que as sequências possam ser repetidas e como os dispositivos eletrônicos são regidos pela lei do acaso, torna-se impossível duplicá-las. A saída para esse impasse é gerar os números aleatórios baseando-se em operações aritméticas, conhecidos como pseudo-aleatórios.

O método de Monte Carlo usa números aleatórios para tomar decisões ao longo da simulação. Para simular as funções de distribuição de probabilidade específica de cada tipo de decisão é necessário que esses números sejam distribuídos de forma não uniforme.

Uma vez conhecido um algoritmo que desenvolva uma série de números aleatórios de forma uniforme, é possível transformá-los em não uniformes, pois a função f necessária para esta transformação é a inversa da função de distribuição não uniforme, g. Isto é, f=g-1.

Referência(s):

TAHA, Hamdy A. Operations research: an introduction . 6.ed. Upper Saddle River: Prentice Hall, c1997.

Luis

A maioria das linguagens de computador possui uma subrotina, objeto e/ou função que irá gerar números aleatórios.

Uma sequência de números alatórios devem ser uniformes e independentes.

Ao se utilizar um método de geração de números, geram-se números pseudo-aleatórios, pois será possível replicar o conjunto de números aleatórios utilizando o mesmo método.

A geração de números pseudo-aleatórios pode acarretar problemas se comparado a números verdadeiramente aleatórios. Alguns problemas são:

1.Os números podem não estar distribuídos uniformemente

2.Os valores podem ser discretos, ao invés de contínuos

3.A média pode ser muito alta ou muito baixa

4.A variância pode ser muito alta ou muito baixa

5.Pode ocorrer dependência entre os números

No entando, existem técnicas para verificar se um gerador de números aleatórios é aceitável ou não.

Caracteristicas básicas de um gerador de números aleatórios:

1. A rotina de geração de números aleatórios deve ser rápida. Operações individuais são pouco custosas, mas para uma simulação que pode requerir milhares de números, o custo pode ser caro.

2.A rotina deve ser portátil para diferentes computadores e, idealmente, para diferentes linguagens de programação. Isso é necessário para garantir que o simulador produza os mesmos resultados em qualquer máquina que o execute.

3.A rotina deve ter um ciclo suficientemente grande, ou seja, deve demorar-se muito tempo para que os números começem a se repetir.

4.Os números aleatórios devem ser replicáveis. Se dadas as condições iniciais deve ser possivel gerar o mesmo conjunto de números aleatórios, completamente idependente do sistema que está sendo simulado. Ideal para comparação de sistemas e debugging.

5.Os números gerados devem estar proximos das condições ideias de uniformidade e independencia.

Inventar tecnicas que aparentam gerar numeros aleatorios é fácil, mas gerar uma sequência que pareçam independentes, distribuidos uniformemente pode ser incrivelmente díficil. Há uma vasta literatura sobre o tópico, estabelecendo caracteristicas e propriedades de vários geradores.

Referência:

Banks, Jerry. Discrete-Event System Simulation . 4.ed. Upper Saddle River: Prentice Hall

Rebeca