Aula 08 Modelagem e Simulação

Prévia do material em texto

1
© UNESP 6 Agosto 2008
PROJETO 2 - LABORATÓRIO
GERADORES DE NÚMEROS 
ALEATÓRIOS COM GOOGLE DOCS
Autor: Anibal Tavares de Azevedo 
MODELAGEM E SIMULAÇÃO
2
© UNESP 6 Agosto 2008
COMO SABER SE UM DADO É JUSTO?
COMO GERAR NÚMEROS ALEATÓRIOS 
(E QUE QUE TENHA UMA CERTO DISTRIBUIÇÃO)?
NA VERDADE: COMO GERAR NÚMEROS 
PSEUDO-ALEATÓRIOS?
3
© UNESP 6 Agosto 2008
Problema Descrição LINK
1 Lab 4 – Exercício 1 https://docs.google.com/spreadsheet/ccc?key=0AozU
GKjaO9uEdE1rd1Y4VHlqS1NhNGtydFZvRzZKOX
c&usp=sharing
2 Lab 4 – Exercício 2 https://docs.google.com/spreadsheet/ccc?key=0AozU
GKjaO9uEdHNZakJjYjhpcmtPZkhFalRxbEN2eEE
&usp=sharing
3 Lab 4 – Exercício 3 https://docs.google.com/spreadsheet/ccc?key=0AozU
GKjaO9uEdFNRTUYzbXZMamd5T045cHdmc0dB
UGc&usp=sharing
GERAÇÃO DE NÚMEROS ALEATÓRIOS
Os exercícios estão disponíveis nos links dados abaixo:
4
© UNESP 6 Agosto 2008
VARIÁVEIS ALEATÓRIAS
Como são gerados números aleatórios no computador?
Valores aleatórios repetição
Na verdade, o computador gera valores pseudo-aleatórios.
10100 valor
5
© UNESP 6 Agosto 2008
Variável Pseudo-aleatória
VARIÁVEIS ALEATÓRIAS
É uma variável cujo valor é obtido a partir de um processo
determinístico e que deve satisfazer certas propriedades dos
números aleatórios. Por exemplo, para um gerador pseudo-
aleatório que gere uma distribuição uniforme U é esperado
que, para um número suficientemente grande de amostras, a
frequência de valores, em faixas de mesmo tamanho, seja
aproxidamente equitativa.
Qual dos histogramas parece ser o de uma uniforme?
6
© UNESP 6 Agosto 2008
Algumas das propriedades desejadas para valores 
pseudo-aleatórios: 
VARIÁVEIS ALEATÓRIAS
•Não apresentar repetição após a geração de poucos
valores;
Exemplo: 2, 1, 3, 2, 1, 3, ...
•Para uma amostra de tamanho suficientemente grande os
valores devem possuir uma frequência de ocorrência
aproximadamente uniforme;
Exemplo: Histograma próximo da uniforme.
•Não deve haver correlação entre valores sucessivos;
Ex.: Sempre após aparecer o valor 2 aparece o valor 1.
•As frequências de ocorrência de valores pseudo-aleatórios
não deve diferir significativamente quando comparadas com
as frequências de sequências aleatórias.
Exemplo: Usar um teste estatístico para comparar os
valores gerados e os esperados: qui-quadrado e Kolmogorov-
Smirnov.
7
© UNESP 6 Agosto 2008
A ruína do apostador
VARIÁVEIS ALEATÓRIAS
Exemplos de problemas que empregam variáveis aleatórias
Passeio aleatório
Como gerar valores com 
estas probabilidades?
8
© UNESP 6 Agosto 2008
VARIÁVEIS ALEATÓRIAS
Gerador Linear Congruencial
mcaXX ii mod)(1 +=+
mXU ii /=
Onde:a, c e m são parâmetros dados e Ui é um valor
aleatório com função de distribuição Uniforme U(0,1).
para i=0, 1, 2, ..., n.
X0 é valor inicial dado.
Observe que neste caso, o gerador linear congruencial é uma
fórmula que depende de um valor inicial Xo. O valor inicial Xo
também é chamado de semente do processo aleatório e toda
a sequência aleatória é determinada por ele.
9
© UNESP 6 Agosto 2008
VARIÁVEIS ALEATÓRIAS
mcaXX ii mod)(1 +=+ para i=0, 1, 2, ..., n.
Supor que: a = 3, 
c = 0, m = 5 e X0 = 4
i Xi 3Xi (3Xi)mod5 Ui = Xi/m
0 4 12 2 4/5
1 2 6 1 2/5
2 1 3 3 1/5
3 3 9 4 3/5
4 4 12 2 4/5
5 2 6 1 2/5
5mod)3(1 ii XX =+
Exercício 1: Reproduzir o exemplo dado a seguir no 
Google docs. Expandir a planilha para 100 valores.
10
© UNESP 6 Agosto 2008
VARIÁVEIS ALEATÓRIAS
Exercício 2: Elaborar um histograma dos valores 
gerados anteriormente para Ui. O que foi obtido e o que 
esperar para uma distribuição uniforme?
Trocar por categorias:
Faixa 1
Valores Ui de 0 até 0,20
11
© UNESP 6 Agosto 2008
F(n)= F(n-1) + F(n-2)
onde: n = 2, 3,... 
e F(0) = F(1) = 1
Espiral de Fibonacci
VARIÁVEIS ALEATÓRIAS
Sequência de Fibonacci 1, 1, 2, 3, 5, 8, 13,...
http://en.wikipedia.org/wiki/Image:Low_pressure_system_over_Iceland.jpg
http://en.wikipedia.org/wiki/Image:Messier51.jpg
http://en.wikipedia.org/wiki/Image:Brassica_romanesco.jpg
12
© UNESP 6 Agosto 2008
VARIÁVEIS ALEATÓRIAS
Gerador Defasado de Fibonacci
mXXX iii mod)*( 21 −−=
mXU ii /=
Onde:a, c e m são parâmetros dados e Ui é um valor
aleatório com função de distribuição Uniforme U(0,1).
para i=0, 1, 2, ..., n.
X0, X1 são dados.
13
© UNESP 6 Agosto 2008
VARIÁVEIS ALEATÓRIAS
Exercício 3: Elaborar um gráfico do tipo 
“Scatter” com os pares (Ui,Ui+1) do Exercício 1.
O que esperar para uma distribuição uniforme?
Ui
Ui+1
i Ui = Xi/m Ui+1
0 4/5 2/5
1 2/5 1/5
2 1/5 3/5
3 3/5 4/5
4 4/5 2/5
5 2/5 -
14
© UNESP 6 Agosto 2008
DADOS DE ENTRADA
Garbage in,Garbage out
Often abbreviated as GIGO, this is a famous 
computer axiom meaning that if invalid data 
is entered into a system, the resulting 
output will also be invalid. Although 
originally applied to computer software, the 
axiom holds true for all systems, including, 
for example, decision-making systems.
15
© UNESP 6 Agosto 2008
DADOS DE ENTRADA
16
© UNESP 6 Agosto 2008
DADOS DE ENTRADA
Como verificar se os valores aleatórios obtidos a
partir de um gerador aleatório, isto é, uma equação,
representa o comportamento esperado para uma certa
função de distribuição de probabilidade? Por exemplo,
como verificar se a sequência produzida segue uma
função de distribuição uniforme U[1,4]?
PROBLEMA:
17
© UNESP 6 Agosto 2008
DADOS DE ENTRADA
Teste de Kolmogorov-Smirnov:
Este teste compara a função de distribuição acumulada
(FDA) esperada F(x) com a FDA observada SN(x), onde N
é o número de observações da amostra.
Se a amostra fornece valores R1, R2, ..., RN, então, a
FDA empírica de SN(x) será dada por:
N
xRRRdeno
xS NN

=
},...,,{.
)( 21
Conforme N torna-se grande, SN(x) deve se tornar uma
melhor aproximação para F(x), provendo, portanto,
evidências de que a hipótese H0 é verdadeira.
18
© UNESP 6 Agosto 2008
H0: R1, R2, ..., RN é uma amostra aleatória da variável
aleatória com distribuição acumulada F(x).
H: R1, R2, ..., RN não é uma amostra aleatória da
variável aleatória com distribuição acumulada F(x).
Observando que:
DADOS DE ENTRADA
O teste de Kolmogorov-Smirnov usa a maior desvio
absoluto entre F(x) e SN(x) no intervalo da variável
aleatória e emprega a seguinte fórmula:
D = max |F(x) – SN(X)| (1)
A distribuição D é conhecida e tabelada como função de
N como dado a seguir.
19
© UNESP 6 Agosto 2008
DADOS DE ENTRADA
Para n>40:
20
© UNESP 6 Agosto 2008
DADOS DE ENTRADA
Passos do Teste de Kolmogorov-Smirnov:
Passo 1: Ordenar os dados do menor para o maior. Se
R(i) corresponder ao i-ésimo menor dado, então:
R(1) ≤ R(2) ≤ ... ≤ R(N)
Passo 2: Calcular: e
Passo 3: Calcular: D = max(D+, D-).
Passo 4: Encontrar o ponto crítico D nas tabelas
anteriores para o nível de significância  e o tamanho
N.
Passo 5: Se D ≤ D, então, a hipótese H0 é aceita, caso
contrário é rejeitada.






−=

+
)(
1
max i
Ni
R
N
i
D





 −
−=

−
N
i
RD i
Ni
1
max )(
1
21
© UNESP 6 Agosto 2008
Exemplo 1: Suponha que cinco números foram 
gerados: 0,44, 0,81, 0,14, 0,05 e 0,93. Aplicar
o teste de Kolmogorov-Smirnov com nível de 
significância  = 0,05 para verificar se os valores
seguem uma função de distribuição de 
probabilidade uniforme.
Os passos 1 e 2 são dados pela seguinte tabela:
R(i) 0,05 0,14 0,44 0,81 0,93
i/N 0,20 0,40 0,60 0,80 1,00
i/N – R(i) 0,15 0,26 0,16 - 0,07
R(i)-(i-1)/N 0,05 - 0,04 0,21 0,13
DADOS DE ENTRADA
22
© UNESP 6 Agosto 2008
Passo 3: Calcular: D = max(D+, D-) = max(0,26, 0,21) = 0,26
DADOS DE ENTRADA
Passo 4: Encontrar o ponto crítico D nas tabelas anteriores
para o nível de significância  = 0,05 e o tamanho N = 5:
D = 0,563
23
© UNESP 6 Agosto 2008
DADOS DE ENTRADA
Passo 5: Se D ≤ D, então, a hipótese H0 é aceita, caso contrário
é rejeitada. Como D = 0,26 ≤ D = 0,563. Lembrando que:
H0: R1, R2, ..., RN é uma amostra aleatória da variável
aleatória com distribuição acumulada F(x).H: R1, R2, ..., RN não é uma amostra aleatória da
variável aleatória com distribuição acumulada F(x).
Como H0 é aceita, então, isto significa que os dados possuem
FDA uniforme de acordo com o teste de Kolmogorov-Smirnov.
24
© UNESP 6 Agosto 2008
ANÁLISE ESTATÍSTICA
Exercício 4: Refazer o exemplo 1 em uma 
planilha do Google Docs.
Exemplo 1: Suponha que cinco números foram 
gerados: 0,44, 0,81, 0,14, 0,05 e 0,93. Aplicar
o teste de Kolmogorov-Smirnov com nível de 
significância  = 0,05 para verificar se os valores
seguem uma função de distribuição de 
probabilidade uniforme.
R(i) 0,05 0,14 0,44 0,81 0,93
i/N 0,20 0,40 0,60 0,80 1,00
i/N – R(i) 0,15 0,26 0,16 - 0,07
R(i)-(i-1)/N 0,05 - 0,04 0,21 0,13
25
© UNESP 6 Agosto 2008
Mini-projeto 3: Gerador aleatório
Elaborar uma planilha Excell que teste o gerador linear
congruencial ou (para gradução)/e (para pós) Fibonacci
Defasado com pelo menos 2 combinações diferentes (se
você é aluno de graduação) e 6 combinações (se você é
aluno de pós) diferentes de parâmetros para a, c, m e
X0 para gerar 1000 valores aleatório com distribuição
uniforme U(0,1). Colocar telas da sua planilha e
figuras dos resultados para cada conjunto de valores.
Analisar os resultados obtidos em termos de histograma
e/ou “scatter plot”. Colocar no formato de artigo.
mcaXX ii mod)(1 +=+
mXU ii /=
mXXX iii mod)*( 21 −−=
26
© UNESP 6 Agosto 2008
Mini-projeto 4: Teste de Kolmogorov-Smirnov
Para cada configuração testada no TEMA 1 aplicar o
teste de Kolmogorov-Smirnov e indicar se os números
gerados podem ser considerados com função de
distribuição uniforme U(0,1). Colocar os valores de D
para cada teste com o gerador aleatório e as
respectivas conclusões. Colocar no formato de artigo.
O teste de Kolmogorov-Smirnov usa a maior desvio
absoluto entre F(x) e SN(x) no intervalo da variável
aleatória e emprega a seguinte fórmula:
D = max |F(x) – SN(X)| (1)
A distribuição D é conhecida e tabelada como função de
N como dado a seguir.
27
© UNESP 6 Agosto 2008
OBRIGADO !!!
FIM !!!