Rascunhos sobre geração de números aleatórios - Histórico de revisão

Ana: /* Rebeca */

2010-11-06T15:15:13Z

Rebeca

Ana: /* Ana */

2010-11-03T11:35:04Z

Ana

Luisguilherme: /* Luis */

2010-11-02T22:34:46Z

Luis

Luisguilherme: /* Luis */

2010-11-02T22:15:51Z

Luis

Luisguilherme: /* Luis */

2010-11-02T22:13:19Z

Luis

Luisguilherme: /* Luis */

2010-11-02T22:11:50Z

Luis

Luisguilherme: /* Luis */

2010-11-02T20:40:39Z

Luis

Luisguilherme: /* Luis */

2010-11-02T20:25:04Z

Luis

Luisguilherme em 20h03min de 2 de novembro de 2010

2010-11-02T20:03:26Z

Alinekax: /* Métodos de Congruência */

2010-11-02T15:02:37Z

Métodos de Congruência

← Versão anterior		Edição de 15h15min de 6 de novembro de 2010
Linha 329:		Linha 329:

	Banks, Jerry. '''Discrete-Event System Simulation''' . 4.ed. Upper Saddle River: Prentice Hall		Banks, Jerry. '''Discrete-Event System Simulation''' . 4.ed. Upper Saddle River: Prentice Hall
−
−	~~==Rebeca==~~

@@ Linha 90: / Linha 90: @@
 onde as variáveis ano, mês, dia, hora, min e seg são valores inteiros.
 ----------
@@ Linha 106: / Linha 111: @@
 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.
+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.

← Versão anterior		Edição de 22h34min de 2 de novembro de 2010
Linha 272:		Linha 272:


−	O valor M é a maior ~~integral~~ tal que i + (M+1)m <= N, ~~tal que~~ N é o número total de valores na sequência.	+	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:		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:

@@ Linha 259: / Linha 259: @@
 Exemplo: Considere a seguinte sequência de números:
-,12   0,01   0,23   0,28   0,89   0,31   0,64   0,28   0,83   0,93
+,12_0,01_0,23_0,28_0,89_0,31_0,64_0,28_0,83_0,93
-,99   0,15   0,33   0,35   0,91   0,41   0,60   0,27   0,75   0,88
+,99_0,15_0,33_0,35_0,91_0,41_0,60_0,27_0,75_0,88
-,68   0,49   0,05   0,43   0,95   0,58   0,19   0,36   0,69   0,87
+,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;
@@ Linha 269: / Linha 269: @@
-O teste requer computação de auto-correlação a cada m números (m também conhecido como lag), 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 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.
@@ Linha 311: / Linha 311: @@
-Se pim > 0 isso significaria uma auto-correlação positiva, onde a cada valor sucessivo (obtido a partir do "lag" 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).
+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 "lag" m.
+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 "lag" m
+Caso pim = 0, significaria que obtivemos independência nos números analisados a cada intervalo m

@@ Linha 260: / Linha 260: @@
 ,12   0,01   0,23   0,28   0,89   0,31   0,64   0,28   0,83   0,93
 ,99   0,15   0,33   0,35   0,91   0,41   0,60   0,27   0,75   0,88
 ,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), 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 é a maior integral tal que i + (M+1)m <= N, tal que 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
@@ Linha 296: / Linha 315: @@
 Caso pim < 0 isso significaria uma auto-correlação negativa, onde há uma alternância de valores altos e baixos a cada "lag" m.
 Caso pim = 0, significaria que obtivemos independência nos números analisados a cada "lag" m

← Versão anterior		Edição de 22h11min de 2 de novembro de 2010
Linha 254:		Linha 254:
	---------------------------------------------------------		---------------------------------------------------------

		+	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), 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 é a maior integral tal que i + (M+1)m <= N, tal que 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 "lag" 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 "lag" m.
		+
		+	Caso pim = 0, significaria que obtivemos independência nos números analisados a cada "lag" m

@@ Linha 240: / Linha 240: @@
 Ei = N/n
-Onde N é o número de observações e n o número de ensaios.
+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).
-Motra-se então que para a distruibuição amostrada Xo^2 é aproximadamente uma distruibuição qui-quadrado com n-1 graus de liberdade.
+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.
 ---------------------------------------------------------------

@@ Linha 226: / Linha 226: @@
 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.
@@ Linha 234: / Linha 256: @@
 Banks, Jerry. '''Discrete-Event System Simulation''' . 4.ed. Upper Saddle River: Prentice Hall
 ==Rebeca==

← Versão anterior		Edição de 20h03min de 2 de novembro de 2010
Linha 190:		Linha 190:

	------------------------------------------------------------------------------		------------------------------------------------------------------------------
		+
		+	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.
		+
		+
		+
		+

	Referência:		Referência:

@@ Linha 43: / Linha 43: @@
 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>
+<math> s_{i} = (\beta *s_{i-1}) mod \alpha </math>
 em que mod é o operador de resto
@@ Linha 49: / Linha 49: @@
 O número inteiro gerado é obtido pela parte não inteira da divisão
-<math>\beta *s_{i-1} / \alpha</math>
+<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.
@@ Linha 57: / Linha 57: @@
 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>
+<math> s_{i} = (\theta* si-1² + \gamma si-1 + \beta) mod \alpha </math>
 =====Métodos de Partição de Palavra=====