topico8_IA707_1s11

Prévia do material em texto

IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 1
Geradores de Números Aleatórios 
Índice 
1 O papel da estatística na engenharia e na ciência .............................................................................. 2 
2 Probabilidade .................................................................................................................................... 4 
2.1 Os conceitos de experimento, espaço amostral e evento.............................................................. 6 
2.2 Axiomas de probabilidade ............................................................................................................ 8 
3 O conceito de variável aleatória ...................................................................................................... 15 
3.1 Distribuições e variáveis aleatórias discretas .............................................................................. 19 
3.2 Distribuições e variáveis aleatórias contínuas ............................................................................. 22 
3.3 Exemplos de funções densidade de probabilidade ...................................................................... 24 
3.4 Média e variância da distribuição ............................................................................................... 25 
3.5 Momentos ................................................................................................................................. 28 
4 Medidas amostrais .......................................................................................................................... 29 
5 Geradores de números pseudo-aleatórios em computador ............................................................. 30 
6 Pseudo-aleatoriedade em computadores digitais ............................................................................ 31 
7 Geradores de números pseudo-aleatórios uniformes ...................................................................... 33 
8 Propriedades adicionais de um GNA ................................................................................................ 34 
9 Geradores lineares .......................................................................................................................... 35 
10 Geradores portáveis ........................................................................................................................ 37 
11 Outros geradores ............................................................................................................................ 40 
12 Testes para geradores de números pseudo-aleatórios ..................................................................... 41 
13 Geradores de Números Pseudo-Aleatórios em Computação Evolutiva ............................................. 43 
14 Distribuição normal a partir de uma distribuição uniforme .............................................................. 46 
15 Referências ..................................................................................................................................... 46 
 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 2
1 O papel da estatística na engenharia e na ciência 
As teorias científicas lidam com conceitos, não com a realidade. Embora elas 
sejam formuladas para corresponder à realidade, esta correspondência é 
aproximada e a justificativa para todas as conclusões teóricas é baseada em 
alguma forma de raciocínio indutivo. 
Athanasios Papoulis 
• Métodos estatísticos fornecem ferramentas importantes para a engenharia, 
com teor descritivo e analítico para operar com a variabilidade presente nos 
dados observados. 
• A estatística lida com a coleta, apresentação, análise e uso de dados em 
tomada de decisão e na solução de problemas. 
• Um estatístico usa as leis fundamentais da probabilidade e da inferência 
estatística para elaborar conclusões acerca de determinado experimento. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 3
• Objetivo: Descrever e modelar a variabilidade e tomar decisões na presença de 
variabilidade (inferência estatística). 
• Fundamento: o modelo deve possuir ao menos um elemento intrinsecamente 
aleatório. 
• A variabilidade é resultante de mudanças nas condições sob as quais as 
observações são feitas, de características do sistema de medidas e do processo 
de amostragem. 
• Exemplo: Amostras de ganho de um transistor 
5,10 / 5,24 / 5,13 / 5,19 / 5,08 
� A informação contida nas amostras demonstra de forma conclusiva que o 
ganho do transistor é menor que 5,50? 
� Quanta confiança pode se ter de que o ganho no transistor está contido no 
intervalo [5,00; 5,30]? 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 4
• Estatística inferencial: estimação pontual de parâmetros; estimação de 
intervalos de confiança; teste de hipóteses; transferência de conclusões das 
amostras para as populações; generalização. 
• Estatística descritiva: aplicação de métodos gráficos e numéricos na 
organização e apresentação da informação em uma forma sucinta. 
2 Probabilidade 
• A probabilidade é a linguagem empregada na fundamentação matemática da 
inferência estatística. Trata-se de uma disciplina exata e desenvolvida a partir 
de um encadeamento lógico de deduções a partir de um conjunto de axiomas 
claramente definidos. 
• Há uma óbvia quebra de continuidade entre os elementos de probabilidade 
apresentados em cursos introdutórios e os conceitos mais elaborados 
necessários nas aplicações do dia-a-dia. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 5
• O importante é observar que, quando se aplica a teoria de probabilidade ao 
mundo real, ela se mostra eficaz. 
• Exemplo 1: As raízes da teoria de probabilidade estão associadas aos jogos de 
azar, em Monte Carlo, no século 17. 
• Exemplo 2: Parte do sucesso da indústria japonesa é atribuída ao emprego de 
métodos estatísticos na produção, gerenciamento e planejamento (não apenas 
gerar relatórios, mas extrair conclusões ou realizar inferências). 
• Exemplo 3: Prévia Eleitoral (procedimento sistemático para elaboração do 
experimento e coleta de dados) 
Coleção de todos os indivíduos (população) 
↓ 
Processo de amostragem 
↓ 
Inferência sobre toda a população 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 6
2.1 Os conceitos de experimento, espaço amostral e evento 
• Experimento é o termo utilizado para indicar a realização de algo, ou a 
observação de algo, que acontece sob certas condições, levando a um 
resultado. 
• Ocasionalmente, a natureza de um experimento faz com que o seu resultado 
seja definido unicamente pelas condições nas quais o experimento é realizado. 
• Na prática, todavia, observa-se que muitos experimentos não apresentam a 
propriedade de repetitividade, mesmo sob condições supostamente idênticas. 
• Este é o caso quando existem fatores que influenciam o resultado, mas que não 
são de conhecimento do experimentador ou que o experimentador não pode 
controlar e, também, quando os fatores que supostamente estão sob controle, 
na verdade não estão. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 7
• O resultado não pode, então, ser predito a partir do conhecimento das 
“condições” sob as quais o experimento foi realizado. Neste caso, fala-se do 
experimento como sendo um “experimento envolvendo o acaso” ou, 
simplesmente, “experimento aleatório”. 
• Devido à imprevisibilidade ou ao elemento do acaso no experimento, o tipo de 
modelo matemático usual envolvendo equações determinísticas é inadequado 
e um novo tipo de estrutura matemática é necessário para representar os 
fenômenos de interesse, denominadosprocessos estocásticos. 
• Uma vez que o resultado do experimento não é previsível, ele vai ser um 
dentre os muitos resultados possíveis. 
• O espaço amostral de um experimento aleatório é o conjunto de todos os 
resultados possíveis do experimento, sendo geralmente denotado por S. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 8
• Normalmente, é interessante focalizar a atenção em subconjuntos do espaço 
amostral S. Para tanto, define-se um evento como qualquer subconjunto E do 
espaço amostral S (E ⊂ S). 
2.2 Axiomas de probabilidade 
• O ingrediente principal do modelo matemático de um experimento aleatório é 
a noção de probabilidade, a qual formaliza o conceito de que alguns eventos 
são mais verossímeis do que outros, em termos de suas frequências de 
ocorrência relativas. 
• Os axiomas de probabilidade permitem a manipulação de combinações de 
eventos (eventos compostos). 
• Seja S um espaço amostral, seja ε uma classe que comporta todos os possíveis 
eventos em S, e seja P uma função de valores reais definida em ε. Então P é 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 9
denominada de função de probabilidade e EP é denominada de 
probabilidade do evento E se os seguintes axiomas forem válidos: 
Axioma 1: Para todo evento E, 10 ≤≤ EP . 
O axioma 1 determina que a probabilidade de que o resultado de um experimento 
está contido em E é algum número real entre 0 e 1. 
Axioma 2: 1=SP . 
O axioma 2 determina que, com probabilidade igual a 1, o resultado está contido 
no espaço amostral S. 
Axioma 3: Para qualquer sequência de eventos mutuamente exclusivos K,, 21 EE 
(isto é, eventos para os quais ∅=∩ ji EE quando ji ≠ ), 
∑
∞
=
∞
=
=
11 i
i
i
i EPEP U 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 10
• Algumas proposições simples podem ser deduzidas a partir dos axiomas 
enumerados acima: 
Proposição 1: Dado que E e Ec são eventos sempre mutuamente exclusivos e, 
visto que SEE c =∪ , pelos Axiomas 1 e 2 temos que: 
cc EPEPEEPSP +=∪==1 . 
• De forma equivalente, a equação acima pode ser escrita como: 
EPEP c −= 1 . 
• Em palavras, a proposição 1 afirma que a probabilidade de um evento não 
ocorrer é igual a 1 menos a probabilidade do evento ocorrer. 
Proposição 2: 
FEPFPEPFEP ∩−+=∪ . 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 11
• Para deduzir a fórmula para FEP ∪ é necessário lembrar que )( FE ∪ pode 
ser escrito como a união de dois eventos disjuntos E e )( FEc ∩ . Assim, 
utilizando o Axioma 3, temos que: 
FEPEP
FEEPFEP
c
c
∩+=
∩∪=∪ )(
 
• Além disto, como )()( FEFEF c ∩∪∩= , obtemos pelo Axioma 3 que: 
FEPFEPFP c ∩+∩= 
• Ou, de forma equivalente: 
FEPFPFEP c ∩−=∩ , 
completando assim a prova de que 
FEPFPEPFEP ∩−+=∪ . 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 12
• Esta proposição pode também ser demonstrada utilizando o diagrama de Venn 
mostrado abaixo. 
S
II IIII
FE
 
• As divisões no diagrama mostram três seções mutuamente exclusivas. Em 
palavras, a seção I representa todos os pontos em E que não estão em F (isto é, 
cFE ∩ ); a seção II representa todos os pontos que estão tanto em E quanto 
em F (isto é, FE ∩ ), e a seção III representa todos os pontos em F que não 
estão em E (isto é, FEc ∩ ). 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 13
• Do diagrama de Venn, observamos que: 
IIIII
III
IIIIII
∪=
∪=
∪∪=∪
F
E
FE
 
• Como I, II e III são mutuamente exclusivos, temos pelo Axioma 3 que: 
IIIII
III
IIIIII
PPFP
PPEP
PPPFEP
+=
+=
++=∪
 
• Mostrando que 
IIPFPEPFEP −+=∪ . 
• Visto que FE ∩=II , temos então: 
FEPFPEPFEP ∩−+=∪ , 
que é conhecida como a lei de adição de probabilidades. 
• Em palavras, pode ser expressa como: 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 14
A probabilidade do evento E ou do evento F ocorrer é a soma de 
suas probabilidades em separado menos a probabilidade de ambos 
ocorrerem. No caso dos eventos E e F serem mutuamente 
exclusivos, eles não terão pontos em comum e, portanto, 
0=∩ FEP . Neste caso, FPEPFEP +=∪ , como já 
indicado pelo axioma 3. 
• Maiores detalhes sobre definições, axiomas, e exemplos envolvendo teoria de 
probabilidade → consultar PAPOULIS (1991, caps. 1 e 2). 
• Dentre os conceitos adicionais mais importantes, e que não serão abordados 
aqui, estão o de probabilidade condicional e o teorema de Bayes (veja 
exemplos 2.9 e 2.11 de PAPOULIS, 1991). 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 15
3 O conceito de variável aleatória 
• Ao se arremessar um dado, é sabido que o valor ξ da face que ficar para cima 
vai ser um número entre 1 e 6, mas não é possível predizer este valor. 
• Quando uma lâmpada entra em operação, o seu tempo de vida ξ também não 
pode ser predito. 
• Nesses dois casos, ξ é uma variável aleatória ou estocástica. 
• ‘Arremesso de dado’ e ‘Lâmpada em operação’ são experimentos. 
• O conjunto {1, 2, 3, 4, 5, 6} e o intervalo real de unidades de tempo [0, +∞) 
são os espaços amostrais correspondentes. 
• São eventos: 
� Número par na face que ficou para cima: E = {2, 4, 6}; 
� Lâmpada com tempo de vida inferior a 400 unidades de tempo: 
E = [0, 400). 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 16
• Logo, uma variável aleatória é uma função que aloca um ponto do espaço 
amostral a cada resultado de um experimento aleatório. Dito de outro modo, 
uma variável aleatória é uma função associada a um experimento, sendo que a 
realização do experimento leva esta variável a assumir um valor dependente 
do acaso, mas pertencente ao respectivo espaço amostral. 
• Cada vez que um experimento é realizado, o resultado obtido indica a 
ocorrência ou não de um determinado evento (subconjunto do espaço 
amostral). 
• Formalização do conceito: Uma variável aleatória ξ é uma função com as 
seguintes propriedades: 
� ξ assume valores no espaço amostral S de um experimento; 
� Para todo evento E ⊂ S, a probabilidade de que ξ assuma um valor x ∈ E 
após a realização do experimento, dada por P〈x ∈ E〉 = P〈E〉, é bem 
definida (embora possa ser desconhecida). 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 17
• Como o evento pode ser qualquer, é possível considerar eventos do tipo: E ≡ x, 
onde x ∈ S. Logo, temos que, para todo x ∈ S, a probabilidade de que ξ valha 
x após a realização do experimento, dada por P〈ξ = x〉 = P〈x〉, é bem definida. 
• Considerando que as probabilidades mencionadas acima são bem definidas, 
para toda variável aleatória, então é sempre possível obter uma função 
distribuição de probabilidade definida em todo o espaço amostral. Geralmente, 
se emprega a função distribuição cumulativa de probabilidade. Para tal, seja 
x ∈ S e suponha que E(z) = {x | x ≤ z}. Então, a função distribuição cumulativa 
de probabilidade associada à variável aleatória ξ é dada na forma: 
zxxPzEPzExPzF ≤==∈=ξ |)()()( 
• Apesar desta definição de função distribuição de probabilidade ser muito 
genérica (atende a qualquer tipo de variável aleatória), apenas uma quantidade 
reduzida de tipos de distribuição são verificados em aplicações práticas. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 18
• Neste ponto do texto, o mais importante é dividir estes poucos tipos em duas 
classes: 
1. Distribuições discretas: ocorrem em experimentos que requerem 
contagem. Exemplos: pessoas com menos de 30 anos, mortes por câncer, 
produtos com defeito. 
2. Distribuições contínuas: ocorrem em experimentosque requerem 
medidas. Exemplos: tensão elétrica, pressão sanguínea, vazão de rio. 
• Para cada uma das duas classes, a respectiva função distribuição de 
probabilidade )(⋅ξF terá sempre associada a si: 
� Uma função massa de probabilidade )(⋅ξf , no caso discreto; 
� Uma função densidade de probabilidade )(⋅ξf , no caso contínuo. 
• Deste modo, o conhecimento do comportamento de uma das funções, )(⋅ξF ou 
)(⋅ξf , em todo o espaço amostral já é suficiente para se obter a outra função. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 19
3.1 Distribuições e variáveis aleatórias discretas 
• Uma variável aleatória ξ e sua distribuição de probabilidade são discretas se o 
espaço amostral (onde ξ assume valores) contém apenas um número finito de 
elementos ou um número infinito, mas contável, de elementos. 
• Neste caso, a função massa de probabilidade assume a forma: 


 ==
=ξ
alhures0
...),2,1( se
)(
jxzp
zf
jj
 
e a correspondente função distribuição de probabilidade é dada por: 
∑ ∑
≤ ≤
ξξ ==
zx
j
zx
j
jj
j j
pxfzF
 que tal
 
 que tal
 
)()( 
onde xj, j=1,2,..., são elementos do espaço amostral. 
• Exemplo: No caso de um dado não-viciado, a variável aleatória ξ, 
representando a face que ficar para cima após o arremesso do dado, tem as 
seguintes funções massa e distribuição de probabilidade: 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 20
f ξ ( z )
1 3 4 5 62
1
6
F ξ ( z )
z1 3 4 5 62
1
2
1
z
 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 21
• Em muitas aplicações, existe o interesse em medidas de probabilidade do tipo 
rq xxP ≤ξ< , ou seja, a probabilidade de que ξ assuma qualquer valor no 
intervalo rq xxx ≤< , onde xq e xr não precisam necessariamente ser 
elementos de S. Da definição zxxPzF ≤=ξ |)( de função distribuição de 
probabilidade, pode-se deduzir que: 
)()( qrrq xFxFxxP ξξ −=≤ξ< . 
• Como a variável aleatória ξ é discreta, resulta: 
∑
≤<
=≤ξ<
rjq xxx
j
jrq pxxP
 que tal
 
. 
• Uma consequência direta é o resultado a seguir: 
1
 que tal
 
=∑
∈Sx
j
j
j
p 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 22
3.2 Distribuições e variáveis aleatórias contínuas 
• Uma variável aleatória ξ e sua distribuição de probabilidade são contínuas se o 
espaço amostral (onde ξ assume valores) contém um número infinito e 
incontável de elementos. 
• Neste caso, valem as seguintes relações entre as funções distribuição )(⋅ξF e 
densidade )(⋅ξf de probabilidade: 
dz
zdF
zf
)(
)( ξξ = e ∫ ∞− ξξ =≤=
z
dxxfzxxPzF )(|)( 
• Como no caso discreto, existe o interesse em medidas de probabilidade do tipo 
rq xxP ≤ξ< , ou seja, a probabilidade de que ξ assuma qualquer valor no 
intervalo rq xxx ≤< , onde xq e xr não precisam necessariamente ser 
elementos de S. Da definição zxxPzF ≤=ξ |)( de função distribuição de 
probabilidade, pode-se deduzir que: 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 23
)()( qrrq xFxFxxP ξξ −=≤ξ< . 
• Para uma variável aleatória ξ contínua, resulta: ∫ ξ=≤ξ<
r
q
x
xrq
dxxfxxP )( 
• Uma consequência direta é o resultado: 1)( =∫
∞+
∞− ξ
dxxf . 
• Exemplo: Uma variável aleatória ξ com distribuição normal, média 0 e 
variância 1, tem como funções densidade e distribuição de probabilidade: 
-3 -2 -1 0 1 2 3
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
z
f ξ
(z
)
Função densidade de probabilidade
-3 -2 -1 0 1 2 3
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
z
F
ξ(
z)
Função distribuição de probabilidade
 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 24
3.3 Exemplos de funções densidade de probabilidade 
• Normal: uma variável aleatória contínua ξ é chamada normal ou gaussiana se 
sua densidade de probabilidade pode ser expressa na forma: 
2
2
2
)(
2
1
)( σ
η−−
ξ πσ
=
z
ezf 
• Uniforme: uma variável aleatória contínua ξ é chamada uniforme no intervalo 
[x1,x2] se sua densidade de probabilidade pode ser expressa na forma: 



 ≤≤
−=ξ
alhures0
 se
1
)(
21
12
xzx
xxzf 
• Binomial: uma variável aleatória discreta ξ tem uma distribuição binomial de 
ordem n se sua densidade de probabilidade pode ser expressa na forma: 
∑
=
−
ξ −δ




=
n
k
knk kzqp
k
n
zf
0
)()( 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 25
• Exemplos: Sabendo que a probabilidade de um evento A ocorrer em um dado 
experimento é p, a probabilidade deste evento A ocorrer k vezes em n ≥ k 
experimentos (sob as mesmas condições) é dada por: 
( ) knk pp
k
n
kAP −−




= 1 vezesocorrer 
e a probabilidade deste evento A ocorrer até k vezes em n ≥ k experimentos 
(sob as mesmas condições) é dada por: 
( )∑
=
−−




=
k
r
rnr pp
r
n
kAP
0
1 vezes atéocorrer 
3.4 Média e variância da distribuição 
• A função distribuição de probabilidade )(⋅ξF , ou equivalentemente a função 
massa ou densidade de probabilidade )(⋅ξf , determinam completamente uma 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 26
variável aleatória. Sendo assim, parâmetros e propriedades (como simetria) da 
variável aleatória podem ser obtidos a partir destas funções de probabilidade. 
• Dado o tipo de distribuição e na presença de simetria, a média e a variância 
passam a descrever completamente a variável aleatória. 
• Definição 1: O valor médio ou a média de uma variável aleatória ξ é dado por: 
� ∑ ξ=ξ
j
jj xfx )( , para o caso discreto (o somatório é sobre todos os 
valores possíveis de j); 
� ∫
∞+
∞− ξ
=ξ dxxxf )( , para o caso contínuo. 
• A média é também conhecida como esperança matemática: E[ξ] = ξ . 
• Por hipótese, é suposto que a série (caso discreto) converge absolutamente e 
que a integral (caso contínuo) existe (tem um valor finito). 
• Definição 2: A distribuição é dita ser simétrica em relação a um valor c se 
)()( zcfzcf −=+ . 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 27
• Teorema 1: Se uma distribuição é simétrica em relação a um valor c e tem 
média ξ , então ξ = c. 
• Definição 3: A variância de uma distribuição é denotada por σ2, sendo dada 
por: 
� ( )∑ ξξ−=σ
j
jj xfx )(
22 , para o caso discreto (o somatório é sobre todos 
os valores possíveis de j); 
� ( )∫
∞+
∞− ξ
ξ−=σ dxxfx )(22 , para o caso contínuo. 
• Por hipótese, é suposto que a série (caso discreto) converge absolutamente e 
que a integral (caso contínuo) existe (tem um valor finito). 
• Com exceção do caso em que f(z) = 1 em um único ponto e se anula alhures, 
para o qual resulta σ2 = 0, em todos os outros casos, sempre vai ocorrer σ2 > 0. 
• Definição 4: A raiz quadrada da variância é denominada desvio-padrão, tendo 
por notação σ. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 28
• Como consequência, a variável aleatória 
σ
ξ−ξ=ξN 
tem média zero e variância unitária. 
3.5 Momentos 
• Definição 5: Para qualquer variável aleatória ξ e qualquer função contínua 
g(⋅): ℜ → ℜ, a esperança matemática de g(ξ) é dada por: 
� [ ] ∑ ξ=ξ
j
jj xfxggE )()()( , para o caso discreto (o somatório é sobre 
todos os valores possíveis de j); 
� [ ] ∫
∞+
∞− ξ
=ξ dxxfxggE )()()( , para o caso contínuo. 
• Tomando ( ) kg ξ=ξ , k = 1, 2, ..., as esperanças matemáticas acima 
representam o k-ésimo momento de ξ. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 29
• Tomando ( ) ( )kg ξ−ξ=ξ , k = 1, 2, ..., as esperanças matemáticas acima 
representam o k-ésimo momento central de ξ. 
• Lembre-se que o operador esperançamatemática é linear, ou seja: 
� [ ] [ ] [ ]2121 xExExxE +=+ ; 
� [ ] [ ]xExE α=α , com α determinístico e constante. 
4 Medidas amostrais 
• Média amostral (N amostras): ∑
=
=
N
k
kxN
x
1
1
 
• Variância amostral: ( )∑
=
−
−
=σ
N
k
k xxN 1
22
1
1
 
• Desvio-padrão amostral: ( )∑
=
−
−
=σ
N
k
k xxN 1
2
1
1
 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 30
• Covariância amostral: ( )( )∑
=
−−
−
=σ
N
k
jjkiikij xxxxN 11
1
 
• Coeficiente de correlação amostral: 
ji
ij
ijr σσ
σ
= 
 
5 Geradores de números pseudo-aleatórios em computa dor 
• Como utilizar o computador digital, a mais precisa e determinística dentre 
todas as máquinas concebidas pela mente humana, para produzir números 
aleatórios? 
• Exploração do nível elevado de redundância: computadores digitais executam 
automaticamente, a cada passo do processo de computação, correções da 
trajetória de seu estado físico por meio da representação binária do estado 
interno de seus componentes. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 31
• Possíveis implicações: vantagens e desvantagens da computação digital. 
• Visto que qualquer programa vai produzir uma saída inteiramente previsível, a 
geração de números aleatórios por parte de computadores digitais representa 
uma impossibilidade conceitual. 
� Sequências geradas por computador digital: pseudo-aleatórias; 
� Saídas de processos físicos intrinsecamente aleatórios: aleatórias. 
Exemplos: Arremesso de um dado, movimento browniano, etc. 
• Será que Deus joga dados? [STEWART, 1989] 
6 Pseudo-aleatoriedade em computadores digitais 
• Poucos livros devotados ao estudo de métodos numéricos para implementação 
computacional abordam números aleatórios [DAHLQUIST & BJORCK, 1974 
(cap. 4); FORSYTHE et al., 1977 (cap. 10)]. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 32
• Definição prática (incompleta) de pseudo-aleatoriedade no contexto de 
sequências geradas por computador digital: em relação aos programas 
computacionais que utilizam suas saídas, um programa determinístico que 
produz sequências pseudo-aleatórias deve ser diferente em todos os aspectos 
mensuráveis e estatisticamente não-correlacionado. 
• Dito de outra forma, dados dois geradores de números pseudo-aleatórios, ao 
acoplá-los independentemente a um programa específico de aplicação, deve-se 
obter o mesmo resultado estatístico. Caso contrário, pelo menos um dos 
geradores é inadequado para a aplicação em questão. 
• Conclusão: O gerador deve ser tão aleatório quanto for requerido pela 
aplicação. 
• Desse modo, um bom gerador para uma dada aplicação pode falhar 
espetacularmente em outras aplicações. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 33
• Felizmente, existem testes estatísticos que contribuem no sentido de avaliar a 
adequação de um dado gerador para cada classe de aplicações [L’ECUYER, 
1992], embora uma aplicação específica possa conduzir um gerador a 
expressar seus “pontos fracos”. 
7 Geradores de números pseudo-aleatórios uniformes 
• Conforme definido por L’ECUYER [1994], um gerador de números pseudo-
aleatórios uniformes em computadores digitais tem um estado que evolui em 
um espaço S, composto por um número finito de estados, de acordo com uma 
recorrência na forma: 
sn = f(sn−1), n ≥ 1, 
sendo que s0 ∈ S é denominada a semente, e f: S → S, é a função de transição. 
No n-ésimo passo, a saída do gerador é dada por un = g(sn), com g: S → [0,1] 
sendo a função de saída. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 34
• A sequência de saída do gerador é, portanto, {un, n ≥ 0}. 
• O espaço de saída poderia ser mais geral, mas é suposto aqui o intervalo [0,1]. 
• Como S é finito, a sequência {un, n ≥ 0} deve ser periódica, possivelmente 
depois de transcorrido um transitório inicial. 
• Se ρ for o período da sequência {un, n ≥ 0}, então é desejável tomar ρ o mais 
próximo possível da cardinalidade de S, para evitar desperdício de memória e 
para permitir a aplicação do gerador em casos de demanda elevada, ou seja, em 
situações em que o gerador é acionado com muita frequência. 
• Para sequências binárias, com un tendo b bits, o valor ótimo para o período é 
ρ = 2b−1. 
8 Propriedades adicionais de um GNA 
• Além do atendimento das condições de aleatoriedade, é importante que um 
gerador de números pseudo-aleatórios em computadores digitais apresente: 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 35
� repetitividade; 
� portabilidade; 
� custo computacional baixo por geração; 
� simplicidade de implementação. 
9 Geradores lineares 
• São geralmente os modelos fornecidos pelos sistemas computacionais. 
• Envolvem a geração de uma sequência I1, I2, I3, ... de inteiros entre 0 e m−1 
pela relação de recorrência 
I aI c mj j+ = +1 ( ) mod , j=1,2,... 
• m é denominado módulo, a e c são inteiros positivos denominados 
multiplicador e incremento, respectivamente. 
• A recorrência vai certamente produzir, para algum j = p ≤ m, I j = Ik (k < j), ou 
seja, ela vai ter um período p ≤ m. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 36
• Se o período for p = m, todo inteiro entre 0 e m−1 vai ocorrer em alguma das 
próximas m iterações, fazendo com que a escolha do valor inicial I0 da 
recorrência (semente da geração pseudo-aleatória) não influa de forma 
significativa no resultado estatístico associado a sequências longas. 
• Vantagem: é um método de geração muito rápido, simples de implementar e 
repetitivo para uma mesma máquina. 
• Desvantagens: não é portável, está preso a uma correlação sequencial e os bits 
menos significativos são “menos aleatórios” que os bits mais significativos. 
• Exemplo 1: Para gerar números inteiros pseudo-aleatórios entre 0 e 9, 
recomenda-se o uso dos bits mais significativos (suponha RAND_MAX = 
32767): 
use I(j) = (int) (10.0*rand()/(RAND_MAX+1.0)); 
no lugar de I(j) = rand()%10; 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 37
• Exemplo 2: Embora existam procedimentos bem menos custosos para a 
geração de sequências pseudo-aleatórias de bits [PRESS et al., 1992 (cap. 7)], é 
possível empregar a ideia da amostragem tipo roullete wheel: divide-se a roleta 
ao meio, associando cada metade a um bit. Mais uma vez estão sendo 
considerados os bits mais significativos. 
10 Geradores portáveis 
• Gerador implementável em qualquer linguagem de programação e em qualquer 
máquina, produzindo sempre o mesmo comportamento estatístico e 
apresentando, para uma mesma semente, a mesma sequência de números. 
• Há evidências, teóricas e empíricas, de que tomando c = 0 na recursão 
I aI c mj j+ = +1 ( ) mod , j=1,2,... 
produz-se resultados tão bons quanto aqueles fornecidos pelos geradores 
lineares com c ≠ 0, se for feita uma escolha cuidadosa para a e m. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 38
• Uma escolha possível é a = 75 = 16807 e m = 231−1 = 2147483647. 
• No entanto, não é possível implementar a recursão (com c = 0) com estes 
valores de a e m em qualquer linguagem de alto nível, já que o produto de a 
por m−1 excede o maior valor admitido para um inteiro de 32 bits. 
• Alternativa 1: Implementação em linguagem de montagem, empregando 
registradores de 64 bits. Desvantagem: esta implementação não é portável. 
• Alternativa 2: Felizmente, existe um algoritmo que permite obter o resultado 
do produto de dois inteiros de 32 bits, módulo uma constante de 32 bits, sem 
utilizar qualquer valor intermediário maior que 32 bits. Este algoritmo está 
baseadona seguinte fatoração para m: 
( )m a fix m
a
m a aq r= ⋅ 




 + = +mod 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 39
onde fix
m
a





 fornece a parte inteira da razão 
m
a
. Para um inteiro z tal que 
0 < z < m−1, pode ser mostrado que, tomando r < q, tanto ( )a z q⋅ mod quanto 
r fix
z
q
⋅ 




 assumem valores inteiros no conjunto { }0 1,...,m− , e que 
( )
( )
az m
a z q r fix
z
q
a z q r fix
z
q
m
mod
mod
mod
=
− ⋅ 




 ≥
− ⋅ 




 +







 se 0
 se < 0
 
• Sugestões para os valores de m, a, q e r: 
m a q r 
231−1 16807 127773 2836 
231−1 48271 44488 3399 
231−1 69621 30845 23902 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 40
• O período destes três geradores portáveis é 231−2 = 2.147.483.646. 
• Observação: Escalonar para o intervalo [0,1]. 
• Repare que a semente 0 nunca deve ser utilizada, da mesma forma que o valor 
0 não vai ser produzido para qualquer semente diferente de 0. 
• Dentre os geradores simples, este é o mais recomendado para aplicação, 
embora possa ainda ser aperfeiçoado [PRESS et al., 1992 (cap. 7)]. 
11 Outros geradores 
• Lineares multivariáveis: I a I a I a I mj j j k j k+ − −= + + +1 0 1 1( ) modL 
• Lineares multivariáveis com incremento pseudo-aleatório: 
I a I a I a I c m
c fix
a I a I a I c
m
j j j k j k j
j
j j k j k j
+ − −
+
− −
= + + + +
=
+ + + +





1 0 1 1
1
0 1 1
( ) modL
L 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 41
• Geradores não-lineares: I I mj j+ =1
2( ) mod 
• Combinação de geradores [L’ECUYER, 1996] 
12 Testes para geradores de números pseudo-aleatóri os 
• Para uma discussão mais aprofundada do que vem a ser aleatoriedade e de 
como detectá-la, veja KNUTH [1981]. 
• De acordo com Kolmogorov, uma sequência infinita de bits é aleatória se ela 
não puder ser descrita por uma sequência menor que ela mesma. ← 
Impossibilidade prática 
• Ser diferente × Ser não-distinguível. 
• Em princípio, todos os procedimentos de teste supõem que um gerador de 
números pseudo-aleatórios em um computador digital é uma função 
determinística que produz uma sequência de números, os quais emulam uma 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 42
variável aleatória definida como um processo de amostragem i.i.d. 
(independent and identically distributed) que resulta na distribuição U(0,1) 
(distribuição uniforme no intervalo [0,1]). 
• Duas classes de testes são comumente empregadas [L’ECUYER, 1992]: 
1. Testes teóricos: são específicos para cada classe de geradores e se concentram 
na estrutura intrínseca de cada gerador para derivar características de 
comportamento da sequência de pontos, ao longo de todo um período. 
2. Testes empíricos: tentam encontrar evidências estatísticas contra a hipótese 
nula: “A sequência é obtida a partir de um processo de amostragem i.i.d. da 
distribuição U(0,1)”. 
• O que pode ser dito a respeito de um gerador de números pseudo-aleatórios 
que passou por todos os testes implementados? 
• Formalmente, nada fica demonstrado, mas é possível aumentar a confiança nos 
resultados obtidos com a utilização deste gerador. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 43
13 Geradores de Números Pseudo-Aleatórios em 
Computação Evolutiva 
• Valores aleatórios são requeridos em praticamente todas as etapas de um 
algoritmo evolutivo: 
� Inicialização da população; 
� Seleção de indivíduos; 
� Definição de pontos de corte para crossover; 
� Definição de genes que sofrerão mutação; 
� Definição de um dentre mais de dois alelos candidatos em operações 
de mutação associadas a atributos descritíveis por um alfabeto finito; 
� Definição de um dentre vários operadores alternativos; 
� Argumento de operadores genéticos mais elaborados (mutação em 
ponto flutuante); etc. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 44
• Estudos recentes sugerem que a escolha do gerador de números pseudo-
aleatórios pode afetar o desempenho de um algoritmo evolutivo, embora de 
forma não-intuitiva (CANTÚ-PAZ, 2002; DAIDA et al., 1999; MEYSENBURG, 
1997; MEYSENBURG & FOSTER, 1999a; MEYSENBURG & FOSTER, 1999b; 
MEYSENBURG et al., 2002). 
• Também é sabido que pequenas modificações no gerador podem causar 
grande variação na qualidade do resultado do processo evolutivo. Por 
exemplo, alterando-se a semente do gerador. 
• Para tanto, testes específicos de qualidade foram definidos de modo a explorar 
diretamente a forma como um algoritmo evolutivo utiliza um gerador de 
números pseudo-aleatórios. 
• Estes testes específicos se mostraram necessários, pois os testes convencionais 
não apresentam correlação significativa com os resultados obtidos. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 45
• Em outras palavras, geradores considerados de baixa qualidade conduzem, em 
alguns casos, a melhores resultados junto ao processo evolutivo quando 
comparados a geradores de melhor qualidade (avaliados segundo testes 
convencionais). 
• Dentre todos os geradores de números pseudo-aleatórios disponíveis, junto à 
comunidade de computação evolutiva o Mersenne Twister (MT) é o mais 
aceito (MATSUMOTO & NISHIMURA, 1998). 
• Cabe destacar também a proposta de MARSAGLIA (2003): Complimentary-
Multiply-With-Carry (CMWC). 
• Também é possível operar com bases de dados que contêm sequências 
binárias puramente aleatórias, que podem ser encontradas em 
〈www.random.org〉. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 46
14 Distribuição normal a partir de uma distribuição uniforme 
• Dispondo de um gerador com distribuição uniforme, uma distribuição normal 
de média µ e variância σ2, ( )2σµ ,~ Nx , pode ser obtida na forma: 
( ) ( )21 2coslog2 uux e π−σ+µ= 
ou então 
( ) ( )21 2senlog2 uux e π−σ+µ= 
com ( )10, 21 ,~ Uuu . Esta é a bem conhecida transformação de Box-Muller 
(BOX & MULLER, 1958). 
15 Referências 
BÄCK, T., FOGEL, D.B. & MICHALEWICZ, Z. (eds.) “Evolutionary Computation 2: Advanced Algorithms 
and Operators, Chapter 24: Efficient implementation of algorithms”, Institute of Physics Publishing, 
2000. 
BOX, G.E.P. & MULLER, M.E. “A note on the generation of random normal deviates”, The Annals of 
Mathematical Statistics, vol. 29, no. 2, pp. 610–611, 1958. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 47
BULMER, M.G. “Principles of Statistics”, Dover, 1979. 
CANTÚ-PAZ, E. “On Random Numbers and the Performance of Genetic Algorithms”, Proceedings of the 
Genetic and Evolutionary Computation Conference (GECCO’02), vol. 1, pp. 311-318, Morgan 
Kaufmann Publishers, 2002. 
DAHLQUIST, G. & BJORCK, A. “Numerical Methods”, Prentice-Hall, 1974. 
DAIDA , J.M., AMPY, D.S., RATANASAVETAVADHANA , M., LI, H. & CHAUDHRI, O.A. “Challenges with 
verification, repeatability, and meaningful comparison in genetic programming: Gibson’s magic” in 
Banzhaf, W., Daida, J., Eiben, A.E., Garzon, M.H., Honavar, V., Jakiela, M. & Smith, R.E. (eds.) 
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’99), vol. 2, pp. 
1851-1858, Morgan Kaufmann Publishers, 1999. 
DOS REIS, S.F. “Introdução ao Estudo de Probabilidade”, Notas de Aula do Curso de Genética 
Populacional Teórica, IB/Unicamp, 2001. 
EVANS, D.H. “Probability and Its Applications for Engineers”, ASQC Quality Press, 1992. 
FORSYTHE, G.E., MALCOLM , M.A. & MOLER, C.B. “Computer Methods for Mathematical 
Computations”, Prentice-Hall, 1977. 
KNUTH, D.E. “The Art of Computer Programming: Seminumerical Algorithms”, Addison-Wesley,Vol. 
2, 2nd edition, 1981. 
KREYSZIG, E. “Advanced Engineering Mathematics”, 7th edition, John Wiley & Sons, 1993. 
L’ECUYER, P. “Testing random number generators”, Proceedings of the 1992 Winter Simulation 
Conference, IEEE Press, pp. 305-313, 1992. 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 48
L’ECUYER, P. “Uniform random number generation”, Annals of Operations Research, vol. 53, pp. 77-
120, 1994. 
L’ECUYER, P. “Combined multiple recursive generators”, Operations Research, vol. 44, no. 5, pp. 816-
822, 1996. 
LINDGREN, B.D. “Statistical Theory”, Macmillan Publishing Company, 1976. 
LIPSCHUTZ, S. “Theory and Problems of Probability”, McGraw-Hill Book Company, 1965. 
MARDIA , K.V., KENT, J.T. & BIBBY , J.M. “Multivariate Analysis”, Academic Press, 1979. 
MARSAGLIA, G. “Random number generators”, Journal of Modern Applied Statistical Methods, vol. 2, 
no. 1, pp. 2-13, 2003. 
MATSUMOTO, M. & NISHIMURA, T. “Mersenne twister: A 623-dimensionally equidistributed uniform 
pseudorandom number generator”, ACM Transactions on Modeling and Computer Simulation, vol. 
8, no. 1, pp. 3-30, 1998. 
MEYSENBURG, M.M. “The effect of pseudo-random number generator quality on the performance of a 
simple genetic algorithm”, Master’s Thesis, University of Idaho, 1997. 
MEYSENBURG, M.M. & FOSTER, J.A. “Random generator quality and GP performance”, in Banzhaf, W., 
Daida, J., Eiben, A.E., Garzon, M.H., Honavar, V., Jakiela, M. & Smith, R.E. (eds.) Proceedings of 
the Genetic and Evolutionary Computation Conference (GECCO’99), vol. 2, pp. 1121-1126, 
Morgan Kaufmann Publishers, 1999a. 
MEYSENBURG, M.M. & FOSTER, J.A. “Randomness and GA performance revisited”, in Banzhaf, W., 
Daida, J., Eiben, A.E., Garzon, M.H., Honavar, V., Jakiela, M. & Smith, R.E. (eds.) Proceedings of 
IA707 - Prof. Fernando J. Von Zuben 
DCA/FEEC/Unicamp 
Tópico 8 – Geradores de Números Aleatórios 49
the Genetic and Evolutionary Computation Conference (GECCO’99), vol. 1, pp. 425-432, Morgan 
Kaufmann Publishers, 1999b. 
MEYSENBURG, M.M., HOELTING, D., MCELVAIN , D. & FOSTER, J.A. “How Random Generator Quality 
Impacts Genetic Algorithm Performance”, Proceedings of the Genetic and Evolutionary 
Computation Conference (GECCO’02), vol. 1, pp. 480-483, Morgan Kaufmann Publishers, 2002. 
MONTGOMERY, D.C. & RUNGER, G.C. “Applied Statistics and Probability for Engineers”, John Wiley & 
Sons, 1994. 
MOOD, A.M. & GRAYBILL , F.A. “Introduction to the Theory of Statistics”, McGraw-Hill Book 
Company, 1963. 
PAPOULIS, A. “Probability, Random Variables, and Stochastic Processes”, Third Edition, McGraw-Hill, 
1991. 
PRESS, W.H., TEUKOLSKY, S.A., VETTERLING, W.T. & FLANNERY, B.P. “Numerical Recipes in C - The 
Art of Scientific Computing”, Cambridge University Press, 2nd edition, 1992. 
ROSS, S. “A First Course in Probability”, Macmillan Publishing Company, 1984. 
STEWART, I. “Does God Play Dice? The New Mathematics of Chaos”, London: Basil Blackwell, 1989. 
WALPOLE, R.E. & MYERS, R.H. “Probability and Statistics for Engineers and Scientists”, Fifth Edition, 
Macmillan Publishing Company, 1993.