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

Edição atual tal como 13h15min de 6 de novembro 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:

<math> s_{i} = (\beta *s_{i-1}) mod \alpha </math>

em que mod é o operador de resto

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

<math> \beta *s_{i-1} / \alpha </math>

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.

<math> s_{i} = (\theta* si-1² + \gamma si-1 + \beta) mod \alpha </math>

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.

Referência:

http://www.phy.ornl.gov/csep/rn/rn.html

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. 137-141, 1987. Disponível em: < http://library.lanl.gov/cgi-bin/getfile?00418729.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:

Wi = (soma_de_j=0_até_k_em_Wij)_mod_(m1_-_1)

é uniformemente distribuida nas integrais de 0 a m1-2.

Testes de Uniformidade e Independencia

1. Teste de Frequência Um teste básico que deve ser feito para validar um novo gerador é o teste de uniformidade. A partir deste é possível medir o nível de aceitação entre a distribuição da amostra dos números gerados e a distribuição uniforme teorizada. Dois diferentes testes podem ser realizados : O Kolmogorov-Smirnov e o teste to qui-quadrado.

1.1 Teste Kolmogorov-Smirnov Este teste compara a função contínua e uniformemente distribuída F(x)com a função empírica Sn(x) obtida das amostras de N observações. Por definição

F(x) = x ;  0 <= x <= 1

Se a amostra dos números gerados é R1,R2,...,Rn, então a função empírica Sn(x) pode ser definida por:

Sn(x) = (números de R1,R2,...,Rn que são <= x) / N

Conforme N aumenta, Sn(x) deve se tornar uma aproximação melhor de F(x), contanto que a hipótese de que a uniformidade exista seja verdadeira. O teste de Kolmogrov-Smirnov é baseado na maior diferença entre F(x) e Sn(x). Ou seja:

D = max |F(x) - Sn(x)|

Esse valor é então tabelado em função de N na tabela de Kolmogrov-Smirnov. Para testar a uniformidade de uma função, seguem-se as seguintes etapas:

Etapa 1: Arrumam-se os valores obtidos em ordem crescente, sendo que o valor R(i) denotará sempre o menor i-ésimo valor das observações:

R1 <= R2 <= .... <= Rn

Etapa 2: Computa-se:

D+ = max(1<= i <=N) {i/n - R(i)} D- = max (1 <= i <=N) {R(i) - (i-1)/N}

Etapa 3: Computar D = max(D+;D-)

Etapa 4: Localizar na tabela o valor critico de D(alpha) para o nível específico de significância alpha e o tamanho da amostra N.

Etapa 5: Se a amostra estatisca D é maior que o valor crítico D(alpha) então a hipótese de que a amostra provém de uma distribuição uniforme é rejeitada. Se D<= D(alpha) então conclui-se que não detectou-se diferenças entre a distruibuição da amostra e a distruibuição uniforme desejada.

1.2 Teste do Qui-quadrado

O teste do qui-quadrado usa a amostra estatística:

Xo^2 = soma (de i=1 até n) ((Oi - Ei)^2)/ Ei

onde Oi é o número observado no i-ésima ensaio e Ei é o número esperado da i-ésima ensaio e n é o número de ensaios. Para uma distruibuição uniforme o número esperado Ei em cada ensaio é dado por:

Ei = N/n

Onde N é o número de observações e n o número de ensaios. A partir destas informações pode-se demonstrar que a distruibuição da amostra de Xo^2 é aproximadamente uma distruibuição qui-quadrado com n-1 graus de liberade. Observação: Um ensaio pode ser enquivalente a um certo número de observações. Exemplo: n = 10 (10 observações equivalem a 1 ensaio).

Após obtido o valor de Xo^2 compara-se com os valores da tabela do qui-quadrado. Caso o Xo^2 obtido seja menor, a hipótese de que se trata de uma distruibuição uniforme não é rejeitada.

Considrações sobre os testes:

-No teste do qui-quadrado é recomendado escolher n e N tal que cada Ei seja maior ou igual a 5. -Tanto o teste de Kolmogorov-Smirnov e o teste do qui-quadrado são aceitáveis para se testar uniformidade contanto que o tamanho da amostra seja grande. -Entre os dois, o teste de Kolmogorov-Smirnov é o mais recomendado. Além disso, o teste de Kolmogorov-Smirnov pode ser aplicado a pequenas amostras enquanto que o teste do qui-quadrado só é válido para amostras muito grandes (N maior ou igual a 50)

2. Teste de Auto-correlação

O teste de auto-correlação preocupa-se em descobrir se há ou não uma relação de dependência ente os números obtidos em uma sequência. Exemplo: Considere a seguinte sequência de números:

0,12_0,01_0,23_0,28_0,89_0,31_0,64_0,28_0,83_0,93

0,99_0,15_0,33_0,35_0,91_0,41_0,60_0,27_0,75_0,88

0,68_0,49_0,05_0,43_0,95_0,58_0,19_0,36_0,69_0,87

Aparentemente, todos estes números parecem ser randômicos e provavelmente passariam pelo teste de frequência apresentado anteriormente. Porém, ao analisarmos a quinta e a décima coluna pode-se verificar que sempre há um número grande naquelas posicões. Como 30 números é uma amostra pequena não é possível afirmar se realmente há alguma relação entre os números obtidos. Será apresentado um método para se afirmar se tal relação existe em uma determinada amostra. Tal relação pode ser números muito altos, muito baixos ou podem se alternar entre muito altos e muito baixos;

O teste requer computação de auto-correlação a cada m números (m também conhecido como lag, será chamado de intervalo m a partir daqui), começando pelo i-ésimo número.Portanto, a auto-correlação entre os seguintes números é de interesse: Ri, Ri+m, Ri+2m, ..., Ri+(M+1)m.

O valor M é o maior número inteiro possível tal que i + (M+1)m <= N, onde N é o número total de valores na sequência. Caso a autocorrelação seja diferente de zero, isso implicaria que há uma falta de independência, portanto o seguinte teste de hipótese é apropriado:

Ho: pim = 0

H1: pim =/= 0 //p aqui é ro

Para valores muito altos de M, a distruibuição do estimador de pim, denotado de ^pim é aproximadamente normal se os valores de Ri, Ri+m, Ri+2m, ...,Ri+(M+1)m são independentes. Portanto, o seguinte teste estatísco pode ser feito:

Zo = ^pim/desvio padrao(denotado por teta) de ^pim //Zo significaria Z zero ou Z0

Onde Zo é distruibuído de forma normal com variância igual a 1, sob a suposição de independência para um M muito grande. As fórmulas de ^pim e desvio padrão de ^pim são dadas por Schmidt e Taylor [1970] conforme seguem:

^pim = (1/M+1)[(soma de k=0 até M) Ri+km * Ri+(k+1)m] -0.25

//^pim é ro com o ^ em cima e im escrito ao lado em letras menores //i + km e i+(k+1)m são escritos pequenos ao lado de R.

e

desviopadrao de ^pim = raiz de 13M + 7 sobre 12(M+1)

Após computar-se Zo, não se rejeita a hipótese Ho de que os números são independentes se -Z(alpha/2) <= Zo <= Z(alpha/2) onde alpha é o nível de significancia e Z(alpha/2) é obtido da tabela abaixo. //adicionar tabela depois

Se pim > 0 isso significaria uma auto-correlação positiva, onde a cada valor sucessivo (obtido a partir do intervalo m) há uma probabilidade maior do que a esperada de se obter valores próximos um do outro (um valor muito alto seguido de outro ou valor muito baixo seguido do outro).

Caso pim < 0 isso significaria uma auto-correlação negativa, onde há uma alternância de valores altos e baixos a cada intervalo m.

Caso pim = 0, significaria que obtivemos independência nos números analisados a cada intervalo m

Referência:

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