Apuntes unidad 2

Materia:

Simulación

Alumna:

Viviana Guadalupe Cerrillo Rojas 11010070

Grado y grupo:

5°”A”

Carrera:

Ing. En Sistemas Computacionales

Prof.:

L. I. Yolanda Meredith García Molina

Río Grande, Zacatecas Septiembre de 2013

Contenido

UNIDAD 2 ......................................................................................................................... 1

NÚMEROS PSEUDOALEATORIOS ............................................................................................ 1

2.1 MÉTODO DE GENERACIÓN DE NÚMEROS PSEUDOALEATORIOS ......... 1

NÚMEROS PSEUDOALEATORIOS ............................................................................ 2

GENERADOR DE NÚMEROS PSEUDOALEATORIOS .......................................... 2

SIMULACIONES (MÉTODOS DE COMPUTACIÓN DIGITAL) ............................... 2

DISTRIBUCIONES COMPONENTES USADAS ........................................................ 2

TÉCNICA MITAD DE CUADRADO .............................................................................................. 3

TÉCNICA DE MULTIPLICADOR CONSTANTE ........................................................................ 3

MÉTODO ADITIVO CONGRUENTE ............................................................................................ 4

2.2 MÉTODO DE MONTECARLO ................................................................................ 5

CORRIDAS ASCENDENTES Y DESCENDENTES ................................................................. 11

EJEMPLO DE PRUEBA DE BONDAD DE AJUSTE CHI CUADRADA .............................. 13

EJERCICIO PRUEBA DE BONDAD DE AJUSTE DE JI CUADRADA ............................... 14

Prueba de bondad de ajuste de kolmogorov-smirnov ....................................................... 15

PRUEBA DE AUTO CORRELACIÓN ........................................................................................ 15

1

UNIDAD 2

NÚMEROS PSEUDOALEATORIOS Conocer la diferencia entre un número aleatorio y un pseudoaleatorios. Identificar y aplicar

los métodos de generación de números pseudoaleatorios. Aplicar e interpretar las pruebas

estadísticas a los números pseudoaleatorios. Seleccionar el generador de números

pseudoaleatorios y utilizar en la unidad siguiente. Aplicar el método de Montecarlo a la

solución de un problema.

2.1 MÉTODO DE GENERACIÓN DE NÚMEROS PSEUDOALEATORIOS

Es aquel obtenido al azar, es decir, que todo número tenga la misma posibilidad de ser

elegido y que la elección de uno de dependa de la elección del otro. Ejemplo: moneda o

dado.

NUMEROS PSEUDOALEATORIOS

Pseudo-falso

Se genera por un algoritmo determinista

-Más rápido

-Tiene un valor de arranque “SEMILLA”

Distribución uniforme:

U (0,1)

La función de los numero Pseudo aleatorios es que a partir de ellos podemos generar

variables aleatorias las cuales están sujetas en el mayor de los casos, a distribuciones

estadísticas que son las que se usan para establecer el comportamiento de materiales,

sucesos, personas etc., en todo proceso de simulación.

Características:

Ajustarse a una distribución u (0,1) Ser estadísticamente independientes (no debe deducirse un numero conduciendo

otros ya generados). Ser reproducibles (la misma semilla debe dar la misma sucesión). Ciclo repetitivo muy largo. Facilidad de obtención. Ocupar poca memoria.

2

NÚMEROS PSEUDOALEATORIOS

Es un número generado en un proceso que aparece producir números al azar, pero

no lo hace realmente. Las secuencias de números pseudoaleatorios no muestran

ningún patrón o regularidad aparente desde un punto de vista estadístico a pesar

de haber sido generadas por un algoritmo completamente determinista, en el que

las mismas condiciones iniciales producen siempre el mismo resultado.

GENERADOR DE NÚMEROS PSEUDOALEATORIOS

(GPAN) Es un algoritmo que produce una sucesión de números que es muy buena

aproximación a un conjunto de aleatorio de números. La sucesión no es aleatoria

en el sentido que queda determinada por un conjunto relativamente de valores

iniciales llamados la esta del GPAN. Las clases más comunes de estos algoritmos

son generadores lineales congruentes, generadores Fibonacci, demorados

desplazamiento de registro con retroalimentación lineal y desplazamiento de

registros con retroalimentación generalizada, entre los algoritmos más recientes

están Blum Blum shub, fortuna y el Mersennetwister

SIMULACIONES (MÉTODOS DE COMPUTACIÓN DIGITAL)

Simulaciones aleatorias con Java Script

Simulaciones aleatorias con Excel (números y letras)

DISTRIBUCIONES COMPONENTES USADAS

Se presentan algoritmos de generación de variables aleatorias de distribuciones

comúnmente usabas:

BERNOULLI: Es la más simple de las distribuciones, toma solo 2 valores que se

denotan como fracaso (x=o) o éxito (x=1) con probabilidades 1-p y p se usa para

modelar de que un resultado sea de una clase específica o tenga una característica

específica por ejemplo: saber si un sistema de computación está funcionando o no.

Saber si un paquete en una red llego a su destino o no

1-p si x=0

F(x) = p si x= 1

3

0 otro casi

Media

Varianza (1-p)

TÉCNICA MITAD DE CUADRADO

1. Considere 2 semillas iniciales X0 y X1 con D dígitos (D>3)

2. Calcule el producto U= X0 ° X1

3. Seleccione los dígitos contrales para obtener la nueva semilla y el aleatorio r2

4. Convierta x0 = x1 y x1= x2 y ejecute el paso 1

Ejemplo:

X0= 1234 x1=3436 x0= 3456 x1=2647

U= 1234* 3436 u= 09148032

U=4264704 x2= 1480

U= 04264704 r3= 0.1480

X2= 2647 r2=0.2647

TÉCNICA DE MULTIPLICADOR CONSTANTE

1. Considere una semilla x0 y un multiplicador K que permanece constante todo el

tiempo

2. Calcule el producto U=X0*k

3. 0btenga los dígitos centrales para obtener una nueva semilla y el numero

aleatorio r2.

Ejemplo:

X0= 123 k= 3456 X0= 2647 k 3456

U=04264704 U=09148032

R1= 0.2647 r3= 0.1480 k= 3456

U= 05114880

R4= 0.1148

4

MÉTODO ADITIVO CONGRUENTE

1. Considere una serie de números

X, x2 x3 x4…… xn 2. Calcule x1=(x1-1+x1-n) mod m R1= x1/m

Ejemplo:

Sea x1=30, X2=26, X3= 39

X4= 43 x5=52 y m=100

X6= (52+35) mod 100

X6= 87 mod 100

X6= 87 R1= 87/100= 87

X7= (87+26) mod 100

X7= 113 mod 100

X7=13 R2 =13/100 =o.13

X8= 13+39/ 100 52/100

X8 = 52 R3 = .52

X9= 52+53/100 = 95/100

R4= .95

5

2.2 MÉTODO DE MONTECARLO

Es un método numérico que permite resolver problemas mediante la simulación de

variables aleatorias.

Para establecer el método suponga que quiere calcular el área de la figura plana 5.

Entendemos pues que si ponemos la figura en un cuadrado unitario y lo dividimos

en sucesión de puntos podríamos decir que:

Si N es el número de puntos en el cuadrado unitario y N el número de puntos en la

figura S sería igual al cociente de N/N

Esto es:

S=N´/N

S= 4/16 = 0.25

La exactitud del cálculo depende del número de punto puesto en la figura

El método de Montecarlo define puntos en la figura por medio de un procedimiento

aleatorio y trata determinar el área calculando el número de puntos establecer en la

figura entre el número de puntos generado.

El método de Montecarlo puede ser aplicado a la simulación de variables que tienen

comportamiento aleatorio.

6

Por ejemplo: Supongamos que tenemos que simular el tipo de automóviles que

llegan a un estacionamiento. Para ello tenemos la siguiente distribución de

probabilidades.

La pregunta ahora:

¿Cómo hacemos para que genere a partir de la generación de un valor aleatorio,

simula la llegada de un tipo de vehículo determinado a este estacionamiento?

f(x) si x =0 f(x) si x =.3 Probabilidad

f(x) si x =1 f(x) si x =.45 total de X

f(x) si x =3 f(x) si x =.? 1= 100%

f(x) si x =4 f(x) si x =.05

Consideramos el principio en el que se basa el método de Montecarlo podemos

considerar a c/u de los posibles valores para que esta función de distribución de

probabilidades como una serie de rectángulos colocados dentro del cuadrado

unitario.

7

Nótese que si lanzamos puntos de forma aleatoria sobre el cuadrado unitario, estos

serán distribuidos en c/u de las categorías, en función de las áreas que representa

c/u de ellos.

Nótese en este sentido la generación de un punto aleatorio: y de su posición en el

cuadrado depende de las coordenadas “x” y “y” que de dicho punto.

El acomodo de los rectángulos lo podemos hacer de modo que la posición de 1

punto sea nada solo por el valor de “x”.

Luego entonces el valor de “x” es el acumulado de cada área para c/u de las

categorías definidas en el problema. Nótese que el valor de “y” no importa debido a

que su rango siempre seria de 0 a 1 para c/u de las categorías.

8

LA PRUEBA DE KOLMOGOROV-SMIRNOV

9

10

11

CORRIDAS ASCENDENTES Y DESCENDENTES

Procedimiento

1. Generar la muestra de tamaño N de números aleatorios. 2. Construir la sucesión binaria de acuerdo al siguiente criterio:

Si rj es menor o igual a rj+1 entonces asignarle a rj el símbolo 0. Si rj es mayor que rj+1 entonces asignarle a rj el símbolo 1.

3. Con base en la distribución X2, efectuar la prueba, donde la frecuencia esperada de las longitudes de corrida i se calculará con:

12

EJEMPLO. Aplicar la prueba de las corridas ascendentes y descendentes a la muestra de números aleatorios del ejemplo anterior. Compararemos a los números por fila, pero es indistinto hacerlo por columna.

0.15 0.31 0.81 0.48 0.01 0.60

0.26 0.34 0.70 0.31 0.07 0.06

0.33 0.49 0.77 0.04 0.43 0.92

0.25 0.83 0.68 0.97 0.11 0.00

0.18 0.11 0.03 0.59 0.25 0.55

Ahora la sucesión binaria es

0 0 1 1 0 1

0 0 0 1 1 0

0 0 1 0 1 1

0 1 0 1 1 0

1 1 0 1 0

Obsérvese que la última celda se deja en blanco, pues no hay con qué número comparar. (Aquí N = 29)

Longitud de corrida i

FE FO (FE-FO)2/FE

1 11.500 11 0.020

2 5.083 5 0.001

3 1.400 2 0.257

4 0.292 -

5 0.005 -

i FE FO (FE-FO)2/FE

1 11.500 11 0.020

>=2 6.483 7 0.004

X02 = 0.024

13

Como el valor calculado de 0.024 es menor que el valor en tablas de Ji-cuadrada

X21.5%= 3.84, no se puede rechazar la independencia de los números aleatorios.

EJEMPLO DE PRUEBA DE BONDAD DE AJUSTE CHI

CUADRADA Un científico de computadoras desarrollo un algoritmo para generar enteros

pseudoaleatorios sobre el intervalo 0-9 codifica el algoritmo y genera 1000 dígitos

pseudoaleatorios. ¿Existe evidencia de que el generador de números aleatorios

trabaja correctamente?

La distribución de los valores 0-9 es uniforme discreta lo cual implica que cada uno

de los enteros debe ocurrir 100 veces

FE=100

Grados de libertad K-1=10-1=9

Tabla de datos

Intervalo FE FO (𝐹𝐸 − 𝐹𝑜)2

FE

0 100 94 (100 − 94)2/100

1 100 93 (100 − 93)2/100

2 100 112 (100 − 112)2/100

3 100 101 (100 − 101)2/100

4 100 104 (100 − 104)2/100

5 100 95 (100 − 95)2/100

6 100 100 (100 − 100)2/100

7 100 99 (100 − 99)2/100

8 100 108 (100 − 108)2/100

14

9 100 94 (100 − 94)2/100

𝑥29.5%=16.92

Si 𝑥𝑜2< 𝑥2 se aprueba que se genera correctamente

3.72< 16.92 ?=cierto

Se aprueba que el algoritmo generador de números aleatorios se genera

correctamente.

EJERCICIO PRUEBA DE BONDAD DE AJUSTE DE JI

CUADRADA

Un científico ha desarrollado un algoritmo para generar enteros pseudoaleatorios

sobre el intervalo 6-10. Codifica el algoritmo y genera 500 dígitos

pseudoaleatorios. Los datos se muestran en la tabla siguiente. ¿Existe evidencia

de que el generador de números aleatorios está trabajando correctamente?

Los valores 6-10 deben seguir la distribución uniforme discreta, la cual implica que

cada uno de los enteros debe ocurrir exactamente 25 veces. Las frecuencias

esperadas E1=100 para i= 6, 7, 8, 9,10.

Puesto que estas frecuencias esperadas pueden estimarse sin que sea necesario

estimar ningún parámetro a partir de los datos de muestra, la prueba resultante de

bondad de ajuste de la ji cuadrada tendrá k-1 = 5-1 = 4 grados de libertad

15

X-2 4.5 = 9.49 X02 = 1.74

Sea alfa = 5% Tenemos (K-1) grados de

libertad, es decir 5-1 = V=4

El valor en la tabla de la distribución de ji cuadrada es X24.5% = 9.49

X02<x2 4.5% 1.74<9.49 La generación del algoritmo es correcta

Prueba de bondad de ajuste de kolmogorov-smirnov

Tabla de distribución

I i= posición que ocupa el número aleatorio Xi en

el vector ordenado

Fn(X) = n en el paso 2

Dn= max|Fn(Xi-Xi’)| para Xi si Dn < Dn, alfa

No se puede rechazar la hipótesis de que los números generados provienen de

una distribución uniforme

PRUEBA DE AUTO CORRELACIÓN Correlación es la relación recíproca entre dos o más cosas (elementos). A veces un grupo de números generados pueden parecer aleatorios, pero existe una relación entre cada cierto número de ellos a partir de alguno específico. Amplitud de Autocorrelación: Es la distancia que existe entre los números de la lista que tiene la relación entre sí. Se da cada n-ésimo número aleatorio e inicia en el elemento i.

Intervalo FE FO

6 100 94 .36

7 100 93 .49

8 100 100 0

9 100 108 .64

10 100 95 .25

16

Esta prueba se aplica con la suposición de los números aleatorios tiene una distribución uniforme e independiente sobre el intervalo de 1 a 0. Conceptos y parámetros que usamos en Autocorrelación Para analizar la correlación general para todos los pares sucesivos de números aleatorios se utiliza la estadística: Densidad de probabilidad

Donde: N es el total de números en toda la serie; Tamaño de la muestra. i es el primer número donde empieza la amplitud de Autocorrelación. m es la amplitud de la Autocorrelación . M es el entero mayor tal que i+(M+1)*m<N Este valor, se obtiene de acuerdo a los valores dados cuidando que se cumpla la condición. Es un parámetro de la fórmula:

Cumpliéndose la condición: i + ( M + 1 ) m < M Desviación estándar de la Autocorrelación

srim (Desviación estándar de la densidad de probabilidad.) La estadística para determinar la significancia de la Autocorrelación para la secuencia propuesta de M+1 números es:

Z significancia de la Autocorrelación que tiene una distribución Normal, con media cero y una varianza de uno, bajo la suposición de independencia.

Nivel de significancia Si se define el nivel de significancia por medio de a y Z 1 - a /2 el valor de Z hace que: P ( Z >= Z 1 - a /2) = a / 2 Se utiliza (a / 2 puesto que se va a tomar en cuenta ambos lados del área bajo la

curva)

17

Para determinar la Autocorrelación se establecen las siguientes Hipótesis; Hipótesis Nula H0��im=0 Los números aleatorios están correlacionados (No son Aleatorios) Hipótesis Alternativa H1��im�0 Los números aleatorios No están correlacionados (Sí son aleatorios)

Criterio de rechazo | Z0| > Z1-�/2 Entonces , si: 1- /2 Z >Z a se rechaza la hipótesis de aleatoriedad.. y si 1- /2 Z Z a £ Se acepta la hipótesis de aleatoriedad. Ejemplo 1 / 2 Falla a rechazar za - / 2 za a / 2 a / 2 Tenemos la Siguiente serie de Números: 0.20,0.96,0.78,0.18,0.09,0.80,0.02,0.53,0.05,0.30,0.70,0.59,0.98,0.03,0.37,0.86,0.73,0.06,0.53,0.25,0.67,0.78,0.33,0.97,0.63,0.25,0.33,0.72,0.91,0.00,0.24,0.64,0.90,0.08,0.33,0.94,0.33,0.16,0.45,0.70,0.18,0.07 A la primer vista, estos números pueden parecer aleatorios. No obstante, al examinar de cerca estos números se ve que existe una relación clara entre cada sexto número, a partir del segundo. Cada uno de estos números varía en magnitud sucesivamente de muy grande a muy pequeño. 0.20,0.96,0.78,0.18,0.09,0.80,0.02,0.53,0.05,0.30,0.70,0.59,0.98,0.90,0.03,0.37,0.86,0.73,0.06,0.53,0.25,0.67,0.78,0.33,0.97,0.63,0.25,0.33,0.72,0.91,0.00,0.24,0.64,0.90,0.08,0.33,0.94,0.33,0.16,0.45,0.70,0.18,0.07. Ejemplo 2 Determínese si el segundo, el séptimo, el doceavo, y el vigésimo segundo de los números aleatorios de la secuencia que sigue están autocorrelacionados.

18

Sea a = 0.1 0.13,0.91,0.11,0.02,0.65,0.33,0.86,0.05,0.25,0.28,0.80,0.82,0.10,0.78,0.88,0.76,0.29,0.20,0.66,0.1 7,0.71,0.45,0.40,0.35. Puesto que nos interesa el grado de Autocorrelación de cada quinto número a partir del segundo, i=2,m=5,N=25 y M= 3.

Z= 2.87 > Z.95= 1.316 por lo tanto se rechaza la hipótesis nula y por lo tanto se considera que los datos son aleatorios.

19

Ejemplo 3 Dados los siguientes números aleatorios .12, .01, .23, .28, .89, .31, .64, .28, .83, .93, .99, .15, .33, .35, .91, .41, .6, .27, .75, .88, .68, .49, .05, .43, .95, .58, .19, .36, .69, .87 Determine si el 3°, 8°, 13° y los siguientes números en la secuencia están autocorrelacionados. Use �=.05, i=3 (iniciando con el 3er. Número), m=5 (cada 5 números), N=30, y M=4 (entero mayor tal que 3+(m+1)5�30 ). Entonces; �35=1/5[(8.23)(.28)+(.28)(.33)+(.33)(.27)+(.27)(.05)+(.05)(.36)=0.05548