02 generación de números aleatorios y prubas de aleatoriedad
Post on 27-Dec-2015
45 Views
Preview:
TRANSCRIPT
Simulación de Sistemas – Semestre 2008 -1
Simulación de Sistemas
Generación de Números y Variables AleatoriasTomado de Ing. Eduardo Carbajal L.
Agenda
Generación de números y variables aleatorias 1. Generación de Números Aleatorios2. Pruebas de aleatoriedad. 3. Variables aleatorias discretas: Bernoulli, Binomial, Poisson.4. Variables aleatorias continuos: Exponencial, Triangular,
Normal, Chi Cuadrado, Weibull.5. Pruebas de bondad de ajuste: Kolmogorov - Smirnov y Chi
cuadrado (2)
Lecturas: Ross, Cap. 3, 4 y 5Banks, Cap. 8 y 9Law, Cap. 6
Son la herramienta para generar eventos de tipo probabilístico, se emplean en modelos que tienen variables estocásticas. En estos modelos emplearemos números aleatorios uniformemente distribuidos entre 0 y 1, a los cuales identificaremos como Ri.
Generación de Números Aleatorios
Números Aleatorios
EjemploSi se quiere simular un sistema de colas es necesario generar el tiempo entre llegadas de los clientes y el tiempo de servicio. Dichas variables se obtiene a partir de distribuciones de probabilidad específica, que para generar/simular un nuevo valor de la variable emplean números aleatorios en su forma mas simple como input.
tiempo entre llegadas tiempo de servicio
Exponencial con media 2 minutos Normal con media de 3 minutos y desviación estándar de 0.8 minutos
R1 =
0.42R2 =
0.25
Expo(2) Norm(3,0.8)
V2 =
2.46
V1 =
0.78
El tiempo entre llegada es 0.78, es decir el siguiente cliente llegará dentro de 0.78 minutos
El tiempo de servicio es 2.46, es decir el cliente terminará de ser atendido dentro de 2.46 minutos
cola
servidor¿Cuándo llega el próximo cliente?
¿Cuándo tiempo durará el servicio?
1. Tienen una distribución uniforme con parámetros a= 0 y b =1.
Generación de Números Aleatorios
Características de los Números Aleatorios
12
)()(
2)(
,1
)(
2abxVAR
baxE
bxaab
xf
Función de densidad:
media:
Distribución Uniforme
varianza:
2. Estadísticamente independientes
3. Su periodo o ciclo de vida debe ser largo
Entonces como Ri es uniformemente distribuido entre 0 y 1:
media : varianza :
(0 + 1) / 2 = 1/2
= 1/12(1 - 0 ) ² / 12
R1, R2, R3, …………., RiSecuencia de números aleatoriosPeriodo o ciclo de vida
R1, R2, R3, …………., Rn = R1
n : Periodo o ciclo de vida, que equivale al número de veces antes que el primer aleatorio de la secuencia se repita
4. Deben ser generados a través de un método rápido
Generación de Números Aleatorios
Características de los Números Aleatorios
5. Deben ser generados a través de un método que no requiera mucho uso de memoria ni almacenamiento.
Para cumplir con estas características el esquema de generación debería producir una secuencia de números entre uno y cero que simule o imite las propiedades ideales de la distribución uniforme y la independencia tan cerca como sea posible.
Generación de Números Aleatorios
Errores posibles en la generación de los Números Aleatorios
Los números generados no están uniformemente distribuidos.
Los números generados son discretos en lugar de continuos.
La media de los números generados es muy alta o baja.
La varianza de los números generados es muy alta o baja.
Los números generados exhiben variación cíclica (auto correlación entre los números, números sucesivos mucho más altos o bajos que el adyacente, varios números sobre la media seguidos de otros bajo la media).
Provisión Externa
Generación de Números Aleatorios
Formas de Generación
CaracterísticasEs un método de generación rápido.
Es posible determinar una secuencia de números generada anteriormente.
Depende de una fuente externa que contengan miles de números
Produce números pseudo aleatorios
Se emplean medios externos para obtener números aleatorios
Generación Física
Generación de Números Aleatorios
Formas de Generación
CaracterísticasEs un método de generación lento. Imposible reproducir una secuencia de números generada
anteriormente.Podrían producir números realmente aleatorios
Se generan números aleatorios empleando algún instrumento físico
Generación Matemática
Generación de Números Aleatorios
Formas de Generación
Se emplean algoritmos matemáticos para crear relaciones de recurrencia en la secuencia de números generados
CaracterísticasEs un método de generación rápido.
Es posible determinar una secuencia de números generada anteriormente.
Produce números pseudo aleatorios
Revisaremos algunos a continuación
Método del Medio Cuadrado (Mid Square Method)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
En general entonces:Se eleva al cuadrado el número Xi-1 y se extraen los k dígitos medios para conformar Xi. Se obtiene el Ri dividiendo Xi entre 10 elevado a la k.
1. Escoger un número inicial (Xo) o semilla con k dígitos.
2. Se eleva al cuadrado dicho número y se obtiene uno (Xo²) que como máximo tendrá 2k dígitos. Si el número no llega a 2k dígitos colocarle ceros a la izquierda
3. Los k dígitos medios de Xo² corresponden a X1 y se emplean para definir el primer número aleatorio. Como el aleatorio por definición debe ser menor que 1, R1 es entonces X1, que tiene k dígitos, dividido entre 10 elevado a la k
Método del Medio Cuadrado (Mid Square Method)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Ejemplo:
63750 X
4064062520 X
0368.036036841 221
2
RX
X
Semilla
Paso 1:
Tiene 4 dígitos. Por tanto k = 4
Paso 2:
6406.025640640 120
1
RX
X
Tiene 8 dígitos. Por tanto cumple la condición de tener 2k dígitos, no es necesario agregar ceros a la izquierda
Paso 3:
Repitiendo nuevamente los pasos se generarían los siguientes números pseudo aleatorios
Método del Medio Cuadrado (Mid Square Method)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Características
Posiblemente el método mas antiguo, propuesto por John von Newmann.
Método con pobres propiedades estadísticas. La “semilla” debe ser escogida cuidadosamente. Problema: Si en algún momento se obtiene un
número de “k” dígitos, los cuales generan al ser elevados al cuadrado, un número donde los “k” dígitos medios son cero, la secuencia de números se degenera.
Método del Medio Producto (Mid Product Method)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
En general entonces:Se multiplican los números Xi-1 y Xi; y se extraen los k dígitos medios para formar Xi+1. Se obtiene el Ri dividiendo Xi entre 10 elevado a la k.
1. Escoger dos números iniciales (X'o y Xo) con k dígitos.2. Se multiplican dichos números y se extraen los k dígitos medios
de la multiplicación. Los cuales forman el número X1. Si el número no llega a 2k dígitos colocarle ceros a la izquierda
3. Como el aleatorio por definición debe ser menor que 1, R1 es entonces X1, que tiene k dígitos, dividido entre 10 elevado a la k Para generar el siguiente aleatorio se repite el algoritmo multiplicando esta vez Xo por X1
Método del Medio Producto (Mid Product Method)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Ejemplo:
63750 XSemilla
Paso 1:
Tienen 4 dígitos. Por tanto k = 4
Paso 2: Tiene 8 dígitos. Por tanto cumple la
condición de tener 2k dígitos, no es necesario agregar ceros a la izquierda
Paso 3:
Repitiendo nuevamente los pasos se generarían los siguientes números pseudo aleatorios
3721'0 X
8395.073839526 210
2
RX
XX
757213231
0'0
XXX
Semillaadiciona
l
7213.075721323 10'0
1
RX
XX
Método del Medio Producto (Mid Product Method)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Características
Bastante similar al método del Medio Cuadrado Método con pobres propiedades estadísticas. La “semilla” debe ser escogida cuidadosamente. Problema: Si en algún momento se obtiene un
número de “k” dígitos, los cuales generan al ser elevados al cuadrado, un número donde los “k” dígitos medios son cero, la secuencia de números se degenera.
Técnica de multiplicación por una Constante (Constant Multiplier Method)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
En general entonces:Se multiplica cada número Xi por la constante C y se extraen los k dígitos medios para formar Xi+1
1. Escoger dos números iniciales: una semilla Xo con k dígito y una constante C.
2. Se multiplican dichos números y se extraen los k dígitos medios de la multiplicación. Los cuales forman el número X1. Si el número no llega a 2k dígitos colocarle ceros a la izquierda
3. Como el aleatorio por definición debe ser menor que 1, R1 es entonces X1, que tiene k dígitos, dividido entre 10 elevado a la k Para generar el siguiente aleatorio se repite el algoritmo multiplicando esta vez X1 por C
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Ejemplo:
63750 XSemilla
Paso 1:
La semilla tiene 4 dígitos. Por tanto k = 4
Paso 2: Tiene 8 dígitos. Por tanto cumple la
condición de tener 2k dígitos, no es necesario agregar ceros a la izquierda
Paso 3:
Repitiendo nuevamente los pasos se generarían los siguientes números pseudo aleatorios
Constante
Técnica de multiplicación por una Constante (Constant Multiplier Method)
3721C
8395.073839526 21
2
RX
CX
7213.075721323 10
1
RX
CX
757213231
0
XCX
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Características
Bastante similar al método del Medio Cuadrado Método con pobres propiedades estadísticas. La “semilla” debe ser escogida cuidadosamente. Problema: Si en algún momento se obtiene un
número de “k” dígitos, los cuales generan al ser elevados al cuadrado, un número donde los “k” dígitos medios son cero, la secuencia de números se degenera.
Técnica de multiplicación por una Constante (Constant Multiplier Method)
Generador Congruencial Lineal(Lineal Congruential Generator)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
OBSERVACIÓN:mod es la función residuo, es decir Zi+1 es el residuo que se obtiene al dividir (aZi+c) entre m
Emplea la fórmula recursiva siguiente:
1,.......,2,1,0,mod)(1
mimcaZZ ii
Donde:
m = módulo, a = multiplicador, c = incremento, Z0 = semilla
No son aleatorios, es una serie Son racionales
Estos cuatro parámetros deben ser enteros no negativos y además:
m > 0, m > a, m > c, m > Z0Para obtener los aleatorios Ri se divide Zi entre m
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Características
Es el generador más utilizado. Produce una secuencia periódica o cíclica de
números aleatorios. Se deben generar secuencias de período completo. Se deben de escoger las constantes a, c y m,
de modo que generen secuencias de período completo.
Generador Congruencial Lineal(Lineal Congruential Generator)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Ejemplo 1: módulo = m = 8multiplicador = a = 5incremento = c = 7semilla = Zo = 4
Parámetros: Generamos entonces aleatorios empleando el GCL:
Generador Congruencial Lineal(Lineal Congruential Generator)
Generador CL: Zi+1 = (5 Zi + 7 ) mod 8
n (5 Zi + 7 ) Zi+1 = (5 Zi + 7 ) mod 8
Ri
1 5*4+7 = 27 27 mod 8 = 3 3/8= 0.375
2
3
4
5
6
5*3+7 = 22 22 mod 8 = 6 6/8= 0.750
5*6+7 = 37 37 mod 8 = 5 5/8= 0.675
5*5+7 = 32 32 mod 8 = 0 0/8= 0
5*0+7 = 7 7 mod 8 = 7 7/8= 0.875
5*7+7 = 42 42 mod 8 = 2 2/8= 0.250
7 5*2+7 = 17 17 mod 8 = 1 1/8= 0.125
8 5*1+7 = 12 12 mod 8 = 4 4/8= 0.500
9 5*4+7 = 27 27 mod 8 = 3 3/8= 0.375
Este GCL permite generar 8 números aleatorios antes de repetir el primero. Su periodo es 8 y es igual al módulo m = 8, se le llama generador de periodo completo
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Ejemplo 2: módulo = m = 10multiplicador = a = 7incremento = c = 7semilla = Zo = 7
Parámetros:
Generamos entonces aleatorios empleando el GCL:
Generador Congruencial Lineal(Lineal Congruential Generator)
Generador CL: Zi+1 = (7 Zi + 7 ) mod 10
n (5 Zi + 7 ) Zi+1 = (5 Zi + 7 ) mod 8
Ri
1 7*7+7 = 56 56 mod 10 = 6 6/10= 0.60
2
3
4
5
7*6+7 = 49 49 mod 10 = 9 9/10= 0.90
7*9+7 = 70 70 mod 10 = 0 0/10= 0
7*0+7 = 7 7 mod 10 = 7 7/10= 0.70
7*7+7 = 56 56 mod 10 = 6 6/10= 0.60
Este GCL permite generar 4 números aleatorios antes de repetir el primero. Su periodo es 4 y es DIFERENTE al módulo m = 10, por tanto no es de periodo completo
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Teorema de Hull y Dobell para GCL que asegure el mayor periodo:
Generador Congruencial Lineal(Lineal Congruential Generator)
El único entero positivo que divide exactamente m y c es 1 (primos relativos).
Si q es un número primo (divisible sólo entre si mismo y 1) que divide m, entonces q debe dividir a -1.
Si 4 divide a m, entonces 4 divide a – 1.
En resumen que buscamos: Periodo largo, buenas propiedades estadísticas, eficiencia computacional y de almacenaje y reproductibilidad.
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
OBSERVACIÓN:El Generador Congruencial Multiplicativo es en realidad un caso específico del Generador Congruencial Lineal cuando el incremento ( c ) es igual a cero. Podemos observar que en el caso de los generadores congruenciales multiplicativos no es posible aplicar el Teorema de Hull y Dubell
Emplea la fórmula recursiva siguiente:
1,.......,2,1,0,mod)(1
mimaZZ ii
Donde:
m = módulo, a = multiplicador, Z0 = semilla
Estos cuatro parámetros deben ser enteros no negativos y además:
m > 0, m > a, m > Z0
Para obtener los aleatorios Ri se divide Zi entre m
Generador Congruencial Multiplicativo ( Multiplicative Congruential Generator)
Generación de Números Aleatorios
Formas de Generación > Generación Matemática
Teoremas para Determinación de parámetros de un GC
Sea: x i+1 = (a x i + c ) mod 2 n
Teorema: Generador con módulo igual a una potencia de 2
Por ejemplo:
n = 8 m = 2n = 28 = 256
c impar c = 7
= P
k = 2 a = 1+4k = 1 + 4(2) = 9
Zi+1 = (9 Zi + 7 ) mod 256
Un generador donde c > 0, n > 1, si c es impar y el factor a es de la forma a = 4k+1 , entonces es de período máximo igual P = 2n
Las pruebas de aleatoriedad son pruebas diseñadas para asegurar que se cumplan las propiedades de uniformidad e independencia deseadas. Algunas son:
Pruebas de Aleatoriedad
Tipos de Pruebas
Prueba de corridas o rachas (runs test):Se utiliza para determinar la presencia anormal de grupos de números ascendentes, descendentes, por encima del promedio, o por debajo del promedio.Prueba de frecuencia:Usa el método de Kolmogorov-Smirnov o el método Chi-cuadrado para comparar una distribución uniforme con la secuencia generada.
Prueba de autocorrelación:Compara la correlación existente entre los elementos de una secuencia con la correlación nula esperada.
Prueba de huecos (gap test):Cuenta los números de dígitos entre dos sucesivas repeticiones y utiliza la prueba de Kolmogorov-Smirnov para comparar esta cantidad con el valor esperado.Prueba de poker:Controla que la frecuencia de aparición de dígitos en una serie de números sea la esperada.
Existen dos:
Pruebas de Aleatoriedad
Pruebas de corridas
Prueba de corridas ARRIBA Y ABAJOPrueba de corridas ARRIBA Y DEBAJO DE LA MEDIA
Se verifica la aleatoriedad de los números, comprobando que el número de corridas sea una variable aleatoria distribuida normalmente. Para eso se emplea una prueba de hipótesis del tipo:
Uniformidad
H0 : Ri ~ U (0,1)
H1 : Ri ≠ U (0,1)
Independencia
H0 : Ri ~ independiente
H1 : Ri ≠ independiente
Para ambas pruebas se debe especificar un nivel de significancia α (Rechazar hipótesis nula dado que es verdadera – 0.01 o 0.05)
Número de corridas
Pruebas de Aleatoriedad
Pruebas de corridas
Corrida: sucesión de eventos similares precedidos y seguidos por un evento diferente.
Corridas:
Sello(S)
Ejemplo: Tirando una moneda - ¿Cuántos eventos hay?
Cara (C)
Si se lanza una moneda 10 veces y se obtienen los resultados siguientes:
C S S C C S S S C S
1 2 3 4 5 6
Número de corridas = 6
Definición
Pruebas de Aleatoriedad
Pruebas de corridas Arriba y Abajo
Esta prueba comprueba si el número total de corridas en la secuencia de números aleatorios puede ser considerada como típica o no. Procedimient
o:1. Se genera una secuencia de números pseudoaleatorios.2. Si a un número le sigue otro mayor se le asigna un “+” , si
el siguiente es menor se le asigna un “-”.3. Se calcula a = número de corridas, cuya longitud está dada
por el número de signos iguales que contiene 4. Siendo N la cantidad de números en la secuencia, la media y la
varianza están dadas por:
312 N
9029162 N
6. Se calcula la longitud de corrida “a”, como la cantidad de grupos de signos asociados a la secuencia de aleatorios. Para N >30 , “a” se puede aproximar mediante una distribución normal . El estadístico de prueba será:
7. Si |Z0| > Z1-/2 entonces no existe evidencia suficiente para decir que los números son aleatorios.
Pruebas de Aleatoriedad
Pruebas de corridas Arriba y Abajo
Procedimiento:
aZ 0
Definición
Pruebas de Aleatoriedad
Pruebas de corridas Arriba y Debajo de la media
Esta prueba nos permite verificar que los datos sigan una distribución uniforme alrededor de la media teórica de 0.5, de forma aleatoria
Procedimiento:1. Se genera una secuencia de números pseudoaleatorios.
2. Si un número está por encima de la media se le asigna un “+” , si está por debajo se le asigna un “-”.
3. Se calcula n1 y n2, donde n1 es el número de observaciones por
encima de la media y n2 el número de observaciones por debajo de
la media4. Siendo N la cantidad de números en la secuencia, la media y la
varianza están dadas por:
)1(
)2(22
21212
N
N
Nnnnn
212
21 Nnn
6. Se calcula la longitud de corrida “b”, como la cantidad de grupos de signos asociados a la secuencia de aleatorios. Para N >30 , “b” se puede aproximar mediante una distribución normal . El estadístico de prueba será:
7. Si |Z0| > Z1-/2 entonces no existe evidencia suficiente para decir que los números son aleatorios.
Pruebas de Aleatoriedad
Pruebas de corridas Arriba y Debajo de la media
Procedimiento:
bZ 0
top related