Carlos Alberto Kamienski ([email protected])
UFABC
INF-103: Avaliação de Desempenho
Geração de Números
Aleatórios
Motivação
Um dos principais passos para a realização de
simulações e experimentações é a geração de
valores aleatórios para algumas variáveis com
alguma distribuição e probabilidade específica,
como normal e exponencial
Procedimento composto de 2 passos


Gerar um número aleatório entre 0 e 1 (uniforme)
Transformar esse número em um valor que satisfaça a
distribuição específica
2
Motivação
Algumas geradores de números aleatórios são
melhores do que os outros
Como gerar números aleatórios para
simulação/experimentação?
O que são números aleatórios adequados para
simulação/experimentação?
Como funciona a geração de números
aleatórios/experimentação?
3
Um gerador simples
O métodos mais comum é usar uma relação
recursiva na qual o próximo número na seqüência
é uma função do último número gerado (ou dos
últimos dois números)

xn = f (xn-1, xn-2, ...)
Por exemplo

xn = 5 xn-1 + 1 mod 16
Começando com x0 = 5

x1 = 5(5) + 1 mod 16 = 26 mod 16 = 10
4
Um gerador simples
Os primeiros 32 números obtidos através do
procedimento acima são

10, 3, 0, 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5 10, 3, 0, 1, 6, 15,
12, 13, 2, 11, 8, 9, 14, 7, 4, 5
Dividindo os xi por 16

0,6250; 0,1875;
0,1250; 0,6875;
0,6250; 0,1875;
0,1250; 0,6875;
0,0000;
0,5000;
0,0000;
0,5000;
0,0625; 0,3750, 0,9375; 0,7500;
0,5625; 0,8750; 0,4375; 0,2500;
0,0625; 0,3750, 0,9375; 0,7500;
0,5625; 0,8750; 0,4375; 0,2500;
0,8125;
0,3125;
0,8125;
0,3125
5
Terminologia
Semente

x0 = valor usado para iniciar a seqüência = 5
Ciclo




Somente os 16 primeiros números são únicos
O 17º é igual ao primeiro
Dado um número, o próximo será sempre o mesmo
O tamanho do ciclo deste gerador é 16
Cauda

Alguns geradores não repetem a parte inicial da seqüência de
números, que é chamada de cauda
Período

O período do gerador é a soma do tamanho da cauda e o
tamanho do ciclo
6
Semente, Cauda, Ciclo, Período
7
Números pseudo-aleatórios
A função f é determinística

Dada a mesma semente, a função f sempre gerará a mesma
seqüência de números
Os números ainda podem ser considerados aleatórios porque
passam em testes de aleatoriedade
Esses números são apenas parcialmente aleatórios
Em simulação, são preferíveis a números totalmente
aleatórios porque é possível repetir os experimentos
Se um resultado diferente é necessário, é possível alterar a
semente
Controle sobre a reprodutibilidade dos experimentos
8
Tipos de Geradores
Geradores congruo-lineares
Geradores de Tausworthe
Geradores de Fibonacci estendidos
Geradores combinados
9
Geradores congruo-lineares
Descobertos por D.H. Lehmer em 1951: Os resíduos de
potências sucessivas de um número têm boas propriedades
aleatórias.
xn = an mod m
Ou de forma equivalente,
xn = a.xn-1 mod m

a multiplicador

m
módulo
Lehmer escolheu os seguintes valores: a = 23 e m = 108
Bom para o ENIAC: máquina com 8 dígitos decimais.
10
Geradores congruo-lineares
Generalizacão (atualmente em uso):
xn = (a.xn-1 + b) mod m
Pode ser analisado utilizando a teoria das
congruências

Geradores Congruo-Lineares Mistos

Geradores Congruo-Lineares (LCG)
misto = possui tanto uma multiplicação por a como uma adicão de b
11
Seleção dos Parâmetros do LCG
a, b e m afetam o período e a autocorrelação
O módulo m deve ser grande

O período nunca será maior do que m
Para o cálculo ser eficiente, m deve ser potência de 2

Assim, mod m pode ser obtido por truncamento
Se b é não-nulo, período máximo m será obtido se e só se:



Os inteiros m e b forem primos entre si.
Todo número primo que for um fator de m deve ser também um fator de a
-1
Se m for múltiplo de 4, a -1 também deve ser múltiplo de 4.
Essas condições são satisfeitas se m = 2k, a = 4c + 1 e b
for ímpar
Onde, c,b e k são inteiros positivos
12
Correlação
Indica a força e a direção do relacionamento
linear entre duas variáveis aleatórias
 Correlação 1: correlação perfeita
 Correlação -1: anti-correlação perfeita
 Correlação 0: nenhuma correlação
Exemplos:

X={1,2,3,4,5}, Y={30,40,50,60,70}, correção = 1

X={1,2,3,4,5}, Z={70,60,50,40,30}, correção = -1

X={1,2,3,4,5}, W={1,10,1,10,1}, correção = 0

X={1,2,3,4,5}, V={1,20,5,10,15}, correção = 0,3746749
13
Auto-Correlação
Medida que informa o quanto o valor de uma
realização de uma variável aleatória é capaz de
influenciar seus vizinhos
Descreve a correlação entre valores da variável
em tempos diferentes
É uma ferramenta matemática usada para
encontrar padrões que se repetem

Ex.: presença de um sinal periódico
Na geração de números aleatórios, demonstra
aleatoriedade dos números
14
Auto-Correlação
X={1,2,3,4,5,6,7,8,9,10,1,2,3,4, 5,6,7,8,9,10,1,2,...}
15
Auto-Correlação
X= “1000 números: distribuição uniforme de 0 a 1”
16
Período x Auto-correlação
Um gerador que possua um período máximo é chamado de
gerador de período completo

xn = (234 + 1) xn-1 + 1 mod 235

xn = (218 + 1) xn-1 + 1 mod 235
É preferível aquele que exibir baixa auto-correlação entre
números sucessivos
Ambos os geradores têm o mesmo período completo, mas
o primeiro tem uma correlação de 0,25 entre xn-1 e xn,
enquanto que o segundo tem uma correlação desprezível
de menos do que 2-18
17
Seleção dos Parâmetros
0.58
Média Empírica
0.56
0.54
m = 231 – 1, a = 4, b = 1
0.52
0.5
m = 482, a = 13, b = 14
0.48
m = 27, a = 26, b = 5
0.46
0.44
m = 9, a = 4,b= 1
0.42
0
500
1000
1500
Tamanho da amostra
2000
18
Recomendações para Escolha da
Semente
Simulações com múltiplas seqüências:

necessitam de mais de uma cadeia de números aleatórios
Fila única = Duas cadeias

Intervalo entre chegadas e tempos de serviços aleatórios
Não usar zero

Pode ser usada com LCGs. Mas, LCGs multiplicativos ou um LCG de Tausworthe ficarão presos
em zero
Evite valores pares. Para LCGs multiplicativos com módulo m = 2k, a
semente deve ser ímpar
* É melhor evitar geradores que possuam muitas restrições sobre os
valores das sementes ou cujo desempenho (período e aleatoriedade)
dependam do valor da semente
19
Recomendações para Escolha da
Semente
3. Não subdivida uma cadeia.
Não gere sementes sucessivas: u1 para gerar intervalos entre chegadas,
u2 para gerar o tempo de serviço implica em Forte correlação
4. Use cadeias que não se superponham. Superposição Correlação.
Ex.: Mesma raiz implica na mesma cadeia
5. Reutilize sementes em replicações sucessivas.
6. Não utilize sementes aleatórias tais como a hora do dia:
Não dá para garantir ausência de superposição
20
Mitos Sobre a Geração de
Números Aleatórios
Um conjunto complexo de operações leva a resultados
aleatórios

É melhor usar operações simples que possam ser avaliadas analiticamente
quanto à sua aleatoriedade
Um teste simples, como o teste do qui-quadrado, é
suficiente para testar a qualidade de um gerador de
números aleatórios. A seqüência 0, 1, 2, ...m-1 passa no
teste do qui-quadrado com uma boa nota, mas falharia num
teste de execução.
Use tantos testes quantos forem possíveis
21
Mitos Sobre a Geração de
Números Aleatórios
Números aleatórios são imprevisíveis. É fácil
obter os parâmetros a,c e m a partir de alguns
números. Isso implica em LCGs serem
inadequados para aplicações de criptografia
22
Mitos Sobre a Geração de
Números Aleatórios
4. Algumas sementes são melhores do que outras.
xn = (9806 xn-1 + 1) mod (217 _ 1)

Funciona corretamente para todas as sementes exceto x0 = 37911

Fica preso em xn = 37911 para sempre

Geradores deste tipo devem ser evitados.



Qualquer semente diferente de zero na faixa válida deveria produzir seqüências de
igual qualidade.
Para alguns a semente deve ser ímpar.
Geradores cujo período ou aleatoriedade dependam da semente não devem ser
usadas, dado que um usuário desavisado pode não se lembrar de seguir todas as
diretrizes.
23
Geração de Valores para Variáveis
Aleatórias (diferentes de U(0,1))
Seja F(x) a distribuição acumulada da função X
A inversa da função F
F 1( y )  inf x : F( x)  y ,0  y  1.
Gerar X como
X  F 1(U )
X  F 1(U )
Exemplo: Exponencial
F ( x )  1  e x
1
X  F (U )   ln(1  U )

1
24
Geração Números Aleatórios Java
25
Geração Números Aleatórios Java
26
Geração Números Aleatórios Java
27
Carlos Alberto Kamienski ([email protected])
UFABC
INF-103: Avaliação de Desempenho
Geração de Números
Aleatórios