Generación de números pseudoaleatorios
description
Transcript of Generación de números pseudoaleatorios
![Page 1: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/1.jpg)
Generación de números pseudoaleatorios
Mg. Samuel Oporto Díaz
SIMULACION DE SISTEMAS DISCRETOS
![Page 2: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/2.jpg)
22/41/41
Objetivo de la Sesión• Exponer los métodos de generación de números aleatorios.
![Page 3: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/3.jpg)
33/41/41
Tabla de Contenido1. Mapa Conceptual
2. Generación de Series de Números Aleatorios.
3. Generadores no congruenciales
4. Generadores congruenciales
![Page 4: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/4.jpg)
44/41/41
Mapa Conceptual del Curso
Modelado y Simulación
Simulación X Eventos
Proyectos Simulación
Colas en Serie
Colas con un servidor
Colas en Paralelo
InventariosSeries de Nro. Aleato
Validación de Series
Generación de VA
![Page 5: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/5.jpg)
55/41/41
Mapa Conceptual
Fenómenos FísicosProcedimientos
Matemáticos
NúmerosAleatorios
Validación deSeries de NA
VariablesU (0,1)
VariablesAleatorias
Tabla de Nros. aleatorios
Xi+1=(aXi+c) mod m
![Page 6: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/6.jpg)
66/41/41
GENERACIÓN DE SERIES DE NÚMEROS ALEATORIOS
![Page 7: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/7.jpg)
77/41/41
Generación de Números Aleatorios• Rol preponderante en el proceso de simulación.
• Para simular necesitamos de números aleatorios como semillas para generar muestras de V.A.
• Características de un generador de nros aleatorios:
• 1) Muestrea valores de Distribución Uniforme.
• 2) Asegura la NO Correlación Serial.
![Page 8: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/8.jpg)
88/41/41
Algunas Propiedades de Nros Aleatorios 1. Distribución Uniforme.
Cualquier número que pertenezca al rango de interés debe tener la misma probabilidad de resultar sorteado.
2. NO Correlación Serial.
La aparición de un número en la secuencia, no afecta la probabilidad de que aparesca otro (o el mismo) número.
![Page 9: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/9.jpg)
99/41/41
EjemploLa sucesión 1,2,3,4,5,1,2,3,4,5,1,2,3,4,5...
es uniforme
pero
está correlacionada.
Existen Tests que verifican las condiciones de uniformidad y correlación serial, temas que veremos mas adelante.
![Page 10: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/10.jpg)
Series de números aleatorios• No tiene sentido el concepto de “número aleatorios”.• Se usa el concepto de “serie de números aleatorios”
• “Una sucesión de números es aleatoria si no puede reproducirse eficientemente mediante un programa más corto que la propia seria”
• “Una sucesión de números es aleatoria si nadie que utilice recursos computacionales razonables en tiempo razonable puede distinguir entre la serie y una sucesión verdaderamente aleatoria de una forma mejor que tirando una moneda fiel para decidir cuál es cuál”
Definiciones provenientes de la teoría computacional
![Page 11: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/11.jpg)
1111/41/41
Serie de Números Aleatorios• Son números que deben de cumplir los requisitos de
espacio equiprobable, es decir, que todo elemento tenga la misma probabilidad de ser elegido y que la elección de uno no dependa de la elección del otro.
![Page 12: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/12.jpg)
1212/41/41
Propiedades deseables1. Uniformemente distribuidos.
2. Estadísticamente independientes (no correlación).
3. Periodo largo (sin repetición).
4. Reproducibles y mutables.
5. Sencillo en su implementación.
6. Portabilidad.
7. Método rápido de generación.
8. Poca memoria para la generación.
![Page 13: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/13.jpg)
1313/41/41
Mecanismos de generación• Tablas de números aleatorios
– RAND (1955), 100,000 números aleatorios (ruido electrónico)
• Fenómenos físicos– Ruido blanco producido por circuitos
electrónicos– Recuento de partículas emitidas– Lanzamiento de monedas– Rueda de la fortuna
• Procedimientos matemáticos– Se usa algoritmos para la generación de
números aparentemente aleatorios, se entrega una semilla y se generan los sucesores mediante una función
1. Uniformemente distribuidos.
2. Estadísticamente independientes.
3. Periodo largo (sin repetición).
4. Reproducibles y mutables.
5. Sencillo en su implementación.
6. Portabilidad.
7. Método rápido de generación.
8. Poca memoria para la generación.
![Page 14: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/14.jpg)
1414/41/41
Generación de Series de # Aleatorios• Es un proceso fundamental en la simulación.• ¿Por qué?
• Para simular el comportamiento de variables aleatorias.– El comportamiento de un sistema depende del comportamiento de sus
variables (variables aleatorias).
• ¿Qué sucede si en un modelo en lugar de usar una distribución Normal usamos una Poisson?
![Page 15: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/15.jpg)
1515/41/41
GENERADORES NO CONGRUENCIALES
![Page 16: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/16.jpg)
1616/41/41
Método del cuadrado medio• Fue propuesto inicialmente por Von Newman y Metrópolis
en el año 1946.
• Para generar el siguiente número pseudo-aleatorio, se toman los n dígitos centrales del cuadrado del número anterior de n dígitos.
• Se requiere una semilla.
![Page 17: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/17.jpg)
1717/41/41
Método del cuadrado medion R(n) R(n)2 M.R(n)2 Val 1 Val 2
0 154 23,716 371 371 0
1 371 137,641 3,764 376 764
2 376 141,376 4,137 413 137
3 413 170,569 7,056 705 056
4 705 497,025 9,702 970 702
5 970 940,900 4,090 409 090
6 409 167,281 6,728 672 728
7 672 451,584 5,158 515 158
8 515 265,225 6,522 652 522
9 652 425,104 2,510 251 510
10 251 63,001 300 300 0
11 300 90,000 0 0 0
12 0 0 0 0 0
![Page 18: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/18.jpg)
1818/41/41
Análisis• El problema con este método es que tiende a degenerar
rápidamente. Dependiendo del valor inicial el método puede degenerar al cabo de ≈20 términos.
• Por ejemplo, supóngase que se quiere generar una serie de números pseudo-aleatorios de cuatro dígitos y se tiene como i-ésimo termino generado es 3500, luego se tendrá:
• Se puede observar que hemos llegado a una condición degenerada. Por la tanto, es necesario verificar siempre la serie de números y protegerse contra este fenómeno
n R(n) R(n)2 M.R(n)2 Random 1 Random 2
i 3500 12250000 2500 0 2500
i+1 2500 6250000 2500 0 2500
![Page 19: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/19.jpg)
1919/41/41
Método del Producto Medio• Este método es muy similar al anterior ya que se tomará
como número aleatorio siguiente de la serie, a los n dígitos centrales del resultado de una multiplicación previa.
• Se requiere dos semillas.
![Page 20: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/20.jpg)
Método del Producto Medio
n R(n) R(n+1) R(n)2 M.R(n)2 Val 1 Val 20 151 155 23,405 340 340 01 155 340 52,700 270 270 02 340 270 91,800 180 180 03 270 180 48,600 860 860 04 180 860 154,800 5,480 548 4805 860 548 471,280 7,128 712 1286 548 712 390,176 9,017 901 0177 712 901 641,512 4,151 415 1518 901 415 373,915 7,391 739 3919 415 739 306,685 668 668 0
10 739 668 493,652 9,365 936 36511 668 936 625,248 2,524 252 52412 936 252 235,872 3,587 358 58713 252 358 90,216 21 21 014 358 21 7,518 51 51 015 21 51 1,071 7 7 016 51 7 357 5 5 017 7 5 35 0 0 018 5 0 0 0 0 0
![Page 21: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/21.jpg)
2121/41/41
Análisis• Una modificación para este método consiste en utilizar un
multiplicador constante, en lugar de dos números aleatorios como se muestra a continuación:
Rn+1 = K * Rn
• Estos métodos son similares al cuadrado medio.• Sin embargo los dos tienen periodos más extensos y los
números parecen estar distribuidos uniformemente. • Este método tiende a degenerar a un valor constante. • Tanto el método de cuadrados medios como el de
producto medio tienen un periodo corto para la cantidad de números aleatorios que vamos a necesitaremos generar en cada uno de nuestros Modelos.
![Page 22: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/22.jpg)
2222/41/41
GENERADORES CONGRUENCIALES
![Page 23: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/23.jpg)
2323/41/41
Generadores Congruenciales• Congruencial Lineal (Mixto).• Congruencial Multiplicativo.
![Page 24: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/24.jpg)
2424/41/41
Método Congruencial Lineal (MCL)• Los generadores congruenciales lineales generan una
serie de números pseudo - aleatorios de tal forma que se puede generar el siguiente a partir del ultimo número derivado, es decir, que el número Xn+1 es generado a partir de Xn.
• La relación de recurrencia para el método congruencial mixto es:
Xn+1 = (aXn + c) mod m
Donde:X0 = semilla (X0 >0)
a = multiplicador (a >0)c = constante aditiva (c >0)m = módulo (m >X0, m >a y m>c)
![Page 25: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/25.jpg)
2525/41/41
Método Congruencial Lineal (MCL)• Si se quiere obtener números Uniformes (0,1) se
normaliza el resultado:
Un = Xn / m
• En el MCL, si se repite un número ya se repite toda la secuencia.
• Ventajas:1. utiliza poca memoria y es muy rápido. 2. fácil de volver a generar la misma secuencia, guardando un solo
número, (se alcanza con partir desde la misma semilla: X0).
![Page 26: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/26.jpg)
2626/41/41
Ejemploa c m1 7 13
n X(n) a*X(n)+c [a*X(n)+c] mod m0 7 14 11 1 8 82 8 15 23 2 9 94 9 16 35 3 10 106 10 17 47 4 11 118 11 18 59 5 12 12
10 12 19 611 6 13 012 0 7 713 7 14 114 1 8 815 8 15 2
![Page 27: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/27.jpg)
2727/41/41
• Si no se escogen los valores adecuados de los parámetros el período del generador de números pseudo – aleatorios, será menor que m.
• En la Tabla A se muestra los valores obtenidos para un generador con parámetros: a = 7, c = 9, X0 = 5 y m = 11. Como puede apreciarse en la tabla el período del generador es 10 que es menor que el módulo que es 11.
• Si bien este caso no es crítico si lo es el que se presenta en la Tabla B donde los parámetros toman los valores de a = X0 = c = 7 y m=10 cuyo período es de 4, que es un caso muy critico que nos puede llevar a resultados no deseables y poco confiables
Análisis
![Page 28: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/28.jpg)
2828/41/41
Tabla Aa c m7 9 11
n X(n) a*X(n)+c [a*X(n)+c] mod m0 5 44 01 0 9 92 9 72 63 6 51 74 7 58 35 3 30 86 8 65 107 10 79 28 2 23 19 1 16 5
10 5 44 0
![Page 29: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/29.jpg)
2929/41/41
Tabla Ba c m7 7 10
n X(n) a*X(n)+c [a*X(n)+c] mod m0 7 56 61 6 49 92 9 70 03 0 7 74 7 56 65 6 49 96 9 70 0
![Page 30: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/30.jpg)
3030/41/41
Selección de m, a, c, X0
a) Selección de módulo (m). Existen dos opciones que son las siguientes:
a.1) Escoger al azar el módulo m.
a.2) Tomar m de tal manera que sea el número primo más grande posible y además que sea menor que pd-1, donde p es la base del sistema que se esta usando y d es el número de bits que tiene una palabra de computadora en el sistema que se esta usando.
Por ejemplo una computadora XT que trabaja en el sistema binario entonces se tiene que p = 2 y d = 16.
![Page 31: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/31.jpg)
3131/41/41
b) Selección de a.• El valor de a debe ser un número entero impar, que no
deberá ser divisible por 3 ó 5. Pero además, para asegurarnos que el generador tenga período completo, el valor que se tome para a deberá escogerse según el siguiente criterio:
(a-1) mod 4 = 0 si 4 es un factor de m.(a-1) mod b = 0 si b es un factor primo de m.
• Generalmente se toma a igual a 2k + 1 cuando se trabaja en el sistema binario. En ambos casos el valor que se asigne a k deberá ser mayor o igual que 2.
Selección de m, a, c, X0
![Page 32: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/32.jpg)
3232/41/41
c) Selección de c.• Este parámetro puede tomar cualquier valor. Pero para
asegurarnos de tener buenos resultados se deberá seleccionar según la siguiente regla:
c mod 8 = 5
• En consecuencia c deberá tomar un valor entero impar y relativamente primo a m.
Selección de m, a, c, X0
![Page 33: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/33.jpg)
3333/41/41
d) Selección de X0
• Se tiene que para el generador congruencial el valor que tome X0 es irrelevante y tiene poca o ninguna influencia sobre las propiedades estadísticas de las series de números pseudo - aleatorios que se generen.
Selección de m, a, c, X0
![Page 34: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/34.jpg)
3434/41/41
Método Congruencial Lineal (MCL)• Para terminar esta parte se debe señalar que existen otras
formas matemáticas de representar este generador, que son las siguientes:
Xn = [anX0 + c{(an - 1)/(a - 1)}] mod m
Xn+k =[anXk + c{(an - 1)/(a - 1)}] mod m
![Page 35: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/35.jpg)
3535/41/41
Método Congruencial Multiplicativo• En forma semejante al método anterior el generador
congruencial multiplicativo genera el próximo número pseudo - aleatorio a partir del último número calculado, siguiendo la siguiente relación de recurrencia:
Xn+1 = aXnmod m
• Para este generador también se deben escoger adecuadamente los valores de a, X0, y m, con la finalidad de que se pueda asegurar un período máximo para la series pseudo - aleatorias generadas por este método. A continuación se dan las reglas que indican como se deben escoger estos valores.
![Page 36: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/36.jpg)
3636/41/41
Selección de m, a, X0
• Para trabajar en el sistema binario los valores de los parámetros deberán escogerse siguiendo las siguientes reglas:
– El valor de X0 debe ser un número entero impar y relativamente primo a m.
– El valor de a debe ser obtenido a partir de la siguiente expresión:a = 8t ± 3
Donde t es cualquier entero.– El valor de m puede ser 2d .
• Si m = 2d el período del generador es 2d-2 ó m/4. • A modo de ejemplo se obtendremos el período de un
generador cuyos parámetros son: a = 5, X0 = 5 y m = 32. En la siguiente tabla se muestra los elementos que componen la serie generada cuyo período es de 8
![Page 37: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/37.jpg)
3737/41/41
Tabla Ca m5 32
n X(n) a*X(n)[a*X(n)] mod m
0 5 25 251 25 125 292 29 145 173 17 85 214 21 105 95 9 45 136 13 65 17 1 5 58 5 25 259 25 125 29
10 29 145 17
![Page 38: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/38.jpg)
3838/41/41
Tabla DParámetros
a b m xo6 0 13 17 0 13 105 0 13 57 0 11 56 0 11 3
Caso Salidas1 6 10 8 9 2 12 7 3 5 4 11 1 6 102 5 9 11 12 6 3 8 4 2 1 7 10 5 93 12 8 1 5 12 8 1 5 12 8 1 5 12 84 2 3 10 4 6 9 8 1 7 5 2 3 10 45 7 9 10 5 8 4 2 1 6 3 7 9 10 4
5
Caso1234
![Page 39: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/39.jpg)
3939/41/41
Streams - Torrentes• Un generador de números aleatorios que comience con la
misma semilla, siempre producirá la misma torrente o secuencia de números.
• Diferentes semillas generarán diferentes secuencias. Si las semillas se eligen con valores no cercanos (en el ciclo del generador), entonces las secuencias de números generados (torrentes) parecerán y actuarán como números aleatorios independientes entre sí con lo que colaborarán en la generación de v.a. Independientes entre sí.
![Page 40: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/40.jpg)
4040/41/41
Tarea 5• Implementar en Excel estos 4 generadores y probar los
métodos de selección.
![Page 41: Generación de números pseudoaleatorios](https://reader033.fdocumento.com/reader033/viewer/2022050908/56814511550346895db1d323/html5/thumbnails/41.jpg)
4141/41/41
PREGUNTAS