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

Edição de 17h03min de 31 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.

Os números reais obtidos pelo gerador encontram-se no intervalo entre 0 e 1. "Cada gerador de números aleatórios utiliza uma função de atualização que a aprtir de um número inteiro (...) retorna outro número inteiro."

Sendo S uma sequência infinita dos números inteiros gerador, pode-se afirmar que esta sequência apresentará repetição de valores em modo cíclico. Denomina-se período a quantidade de valores em cada ciclo.

Pode-se reproduzir uma mesma sequência utilizando a mesma semente, e obtém-se sequências distintas utilizando sementes também distintas. Porém, sequências de sementes distintas podem ter o mesmo ciclo.

Um bom gerador de números aleatórios deve fornecer sequências com períodos grandes e valores uniformemente distribuídos e, ao mesmo tempo, requerir 'pouca' memória e ser facilmente reproduzido.

Apesar de os geradores de números aleatórios serem usualmente determinísticos, estatisticamente as sequências geradas são tão aleatórias quanto uma sequência verdadeiramente aleatória.

Métodos de Congruência

Dentre os métodos existentes para a geração de números aleatórios, o da congruência multiplicativa é o mais empregado. Este método utiliza dois parâmetros inteiros (alfa e beta) além da semente s0. O número inteiro gerado é obtido através da equação:

si = (beta s(i-1)) mod alfa

em que mod é o operador de resto

O número inteiro gerado é obtido pela parte não inteira da divisão

Beta s(i-1) / alfa

Definir parâmetros alfa e beta que gerem números aleatórios para quaisquer sementes é difícil. Uma regra geral é a de que beta não podeser divisível por alfa, evitando-se assim que si = 0.

Nota-se também que o menor i para o qual si = s0 equivale ao período da sequência.

Usualmente, os métodos de congruência utilizam regras de atualização conforme equação abaixo, nas quais alfa, beta, gama e teta são parâmetros inteiros.

si = (teta si-1² + gama si-1 + beta) mod alfa

Métodos de Partição de Palavra

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> . 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])

Para inicializar, o algoritmo requer uma semente inicial <math>x_0</math>, que deve ser fornecida através de algum meio. Para satisfazer condições de períodos para qualquer módulo M, a semente deve ser definida para um valor constante inicial, como um grande número primo (a semente deve ser ímpar, para satisfazer as condições de qualquer módulo). Uma sugestão para se obter a semente x0:

<math>x_0 = ano + 100 * (mês – 1 + 12 * (dia – 1 + 31 * (hora + 24 * (min + 60 * seg))))</math>

onde as variáveis ano, mês, dia, hora, min e seg são valores inteiros.

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 aleató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 e parâmetros iniciais.

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.

Técnicas para se gerar números aleatórios

1. Método de congruência linear

O método de congruência linear produz uma sequência de integrais X1,X2,...., entre zero e m-1 sempre seguindo a relação recursiva:

<math>Xi+1 = (aXi + c) mod m, i=0,1,2,....</math>

Mod fornece o resto da divisão de (aXi + c) por m.

Sendo o valor inicial Xo a semente, a é chamado de multiplicador, c o incremento e m é o modulo. Se c =/= 0 a forma é chamada de mixed congruential method (método de congruência mista) e quando c=0 a forma é chamada de multiplicative conguential method (método de conguência multiplicativa). A escolha de Xo, a, c e m afeta drasticamente as propriedades estatisticas e a duração do ciclo de geração de números aleatórios. Variações da fórmula acima são comuns na geração de números aleatórios.

A fórmula acima gera integrais randômicas ao invés de váriaveis aleatórias. Podem-se gerar variáveis aleatórias entre 0 e 1 com a fórmula:

<math>Ri = Xi/m , i=0,1,2.....</math>

Além disso devemos verificar se os números R1, R2,... possuem uma uniformidade e independência aproximadas. Além disso há várias propiedades secundárias que devem ser consideradas e essas incluem densidade máxima e máximo período.

Densidade máxima se refere que os valores de Ri, i =1,2,...., não deixarão espaçamentos grandes no intervalo [0,1].

Máximo Périodo pode ser conseguido com uma escolha apropriada para a,c,m e Xo. Isso permite conseguir densidade máxima e evita a recorrência de uma mesma sequência de números gerados (também chamado de cycling).

2. Geradores de conguência linear combinados

Com o aumento do poder computacional a complexidades dos sistemas capazes de serem simulados também aumentou. O gerador anterior pode não ser ideal para todas as aplicações necessárias. Uma das soluções encontradas foi combinar dois ou mais geradores de congruência multiplicativa de tal modo que ,quando combinados, possuam boas propriedades estatísticas e períodos muito maiores. O seguinte resultado de L'Ecuyer[1988] sugere que se Wi,1; Wi,2;...;Wi,k são quaisquer váriaveis randomicas discretas e independentes, mas apenas pelo menos uma delas também é uniformemente distribuída nos intervalos 0 a m1 - 2, então:

<math>Wi = (soma_{j=0}^\k\Wij)mod(m1-1) </math> Referência:

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

Rebeca