Números Pseudoaleatorios

Números pseudoaleatoriosEn los experimentos de simulación es necesario generar valores para las variables aleatorias representadas estas por medio de distribuciones de probabilidad. Para poder generar entradas estocásticas (probabilísticas) para un modelo de simulación, se debe contar con un generador de números pseudoaleatorios. Con estos y métodos de generación de variables aleatorias, se pueden simular las entradas incontrolables para un modelo de simulación. Inicialmente los números aleatorios se generaban en forma manual o mecánica utilizando técnicas como ruedas giratorias, lanzamientos de dados, barajas. También existen métodos aritméticos que permiten generan un gran conjunto de números aleatorios, pero el advenimiento de la computadora ha permitido crear generadores que permitan generar de manera sucesiva todo los números aleatorios que se requieran. Características que deben tener un generador de números aleatorios  Debe ser rápido. O sea, generar un número en menor tiempo posible. Esto es importante en función de que el tiempo de computadora suele ser costoso.  El programa debe ser breve. Esto quiere decir que no debe requerir de grandes cantidades de almacenamiento, puesto que ello representa por lo general un alto costo en los sistemas de cómputo.  No debe reciclar las sucesiones de números aleatorios, esto quiere decir que no es deseable que después de cierta cantidad de números generados reaparezca la misma secuencia de números. Cabe aclarar que no necesariamente se reciclara comenzando por el primer número generado, sino que puede comenzar a reproducir la serie a partir de cualquiera de ellos.  Debe ser capaz de reproducir las mismas series de números o bien otras claramente distintas cuantas veces se desee.  El generador debe ser de naturalez no degenerativa, o sea, no debe llegar a un punto en el que continuamente se genera un mismo número. Métodos de Cuadrados Medios: el procedimiento de obtención de números pseudoaleatorios con este tipo de generador es el siguiente: • Se define una semilla. • Se eleva la semilla al cuadrado. • Dependiendo de la cantidad de dígitos que se desea tenga el número pseudoaleatorio, se toman de la parte central del número resultante en el paso anterior el número de dígitos requeridos. Si no es posible determinar la parte central, se completa el número agregando ceros al principio o al final. • Debe tenerse en cuenta que se desean números pseudoaleatorios entre 0 y 1, en consecuencia el resultado se debe normalizar, es decir, si los números son de dos dígitos se normaliza dividiendo por 100, si es de tres dígitos por mil y así sucesivamente. Uno de los inconvenientes de este método es que dependiendo del valor inicial el periodo suele ser corto y tiende a repetirse o a degenerarse. Ejemplo: generar 3 números aleatorios de 4 dígitos a partir de un generador de cuadrados medios utilizando como semilla el número 445. Como se quieren números pseudoaleatorios Ri de 4 dígitos, se tomarán los cuatro dígitos de la parte central del cuadrado de la semilla, de la siguiente manera: (445)^2=198025 = 9802 luego R1= 9802 / 10000 = 0.9802 (9802)^2 = 96079204 = 0792 luego R2 = 0792 / 10000 = 0.0792 (792)^2 = 627264 = 2726 luego R3 = 2726 / 10000 = 0.2726 Método de Producto medio: este método es un poco similar al anterior pero se debe comenzar con dos semillas cada una con k dígitos, el número resultante se toma como las cifras centrales del producto de los dos números anteriores. Xn+1= (Xn)(Xn-1) Pasos:  Seleccione dos números aleatorios o semillas Xn y Xn-1, cada uno con P dígitos.  Multiplique Xn por Xn-1.  Del producto seleccione a los P dígitos centrales e igualese a Xn+1.  Repitase sucesivamente el proceso cuantas veces sea necesario. Por ejemplo, tomando como semillas a X0 =13 y X1 =15 el método sería el siguiente: X2 = (13*15)= 0195 = 19, luego R2 =19 / 100 = 0.19. X3 = (15*19) = 0285 = 28, luego R3 = 28 / 100 = 0.28. X4 = (19*28) = 0532 = 53, luego R4=53 / 100 = 0.53. Método del producto medio modificado: consiste en usar una constante multiplicativa en lugar de una variable. Es decir Xn+1 = (K*Xn). Debe notarse que los métodos anteriores tienen periodos relativamente cortos, los cuales son afectados grandemente por los valores iniciales que se escojan, además son estadísticamente insatisfactorios. También debe tenerse en cuenta que un generador con un periodo corto no sirve para hacer un número considerado de ensayos de simulación. Ejemplo: supóngase que desea producir una secuencia de números aleatorios de tres dígitos por este método, siendo k=618 y Xn=151. N K Xn R*Xn Xn+1 1 618 151 93318 331 2 618 331 204558 455 3 618 455 281190 119 4 618 119 73542 354 . . . . . . . . . . . . . . . MÉTODOS CONGRUENCIALES. Se han desarrollado básicamente tres métodos de congruenciales para generar números pseudoaleatorios, los cuales se derivan del empleo de diferentes versiones de la relación fundamental de congruencia. El objetivo de cada uno de los métodos es la generación en un tiempo mínimo, de sucesiones de números aleatorios con periodos máximos. Los métodos congruenciales son: el aditivo, el multiplicativo y el mixto. Método Congruencial Aditivo: calcula una sucesión de números pseudoaleatorios mediante la relación Xn+1= Xn +Xn-1 (mod M). Para usar este método se necesitan k valores iniciales, siendo k entero. Las propiedades estadísticas de la secuencia tienden a mejorarse a medida que k se incrementa. Este es el único método que produce periodos mayores que M. Ejemplo: supongamos que Xn=1 y Xn-1=1, M=1000 entonces N Xn Xn-1 Xn+1 0 1 1 2 1 2 1 3 2 3 2 5 3 5 3 8 4 8 5 13 5 13 8 21 6 21 13 34 El resultado representa la serie de Fibonacci. Método Congruencial Multiplicativo: calcula una sucesión Xn de enteros no negativos, cada uno de los cuales es menor que M mediante la relación Xn+1= a.Xn (mod M). Es un caso especial de la relación de congruencia en que c=0, este método se comporta de manera satisfactoria estadísticamente, es decir, los números generados por medio de este método están uniformemente distribuidos, y no están correlacionados. Este método tiene un periodo máximo menor que M, pero se pueden imponer condiciones en a y X0 de tal forma que se obtenga el periodo máximo. Desde el punto de vista computacional es el más rápido de todos. Ejemplo: suponga que m=32, a=5 y Xn=7, en este ejemplo el periodo máximo esperado es de p=m/4=8 N Xn 5Xn Xn+1 0 7 35 3 1 3 15 15 2 15 75 11 3 11 55 23 4 23 115 19 5 19 95 31 6 31 155 27 7 27 135 7 8 7 35 3 9 3 15 15 10 15 75 11 Método Congruencial Mixto o Lineal: los generadores congruenciales lineales generan una secuencia de números pseudoaleatorios en la cual el próximo número pseudoaleatorio es determinado a partir del último número generado, es decir, el número pseudoaleatorio Xn+1 es derivado a partir del número pseudoaleatorio Xn La relación de recurrencia para el generador congruencial mixto es Xn+1 =(a Xn+c) mod m, en donde • X0 = es la semilla • a =el multiplicador • c = constante aditiva • m = el modulo (m > X0, a,c) • X0, a, c >0 Esta relación de recurrencia nos dice que Xn+1 es el residuo de dividir a Xn+c entre el modulo. Lo anterior significa que los valores posibles de Xn+1 son 0,1,2,3 ....m-1, es decir, m representa el número posible de valores diferentes que pueden ser generados. Cuando se quiere construir un generador de números aleatorios para simular los valores de una variable aleatoria, se deben elegir los parámetros de tal manera que se garantice un periodo largo para que se puedan hacer todos los ensayos de simulación, por lo tanto se deben tener en cuenta las siguientes condiciones: •a debe ser un número impar, no divisible ni por 3 ni por 5. •c usualmente puede ser cualquier constante, sin embargo, para asegurar buenos resultados, se debe seleccionar a de tal forma que, a mod 8 = 5 para una computadora binaria, o a mod 200 = 21 para computadora decimal. •m debe ser el número entero más grande que la computadora acepte. De acuerdo con Hull y Dobell, los mejores resultados para un generador congruencial mixto en una computadora binaria son: • c = 8*a±3 • a = cualquier entero • X0 = Cualquier entero impar. • M = 2b donde b >2 y que m sea aceptado por la computadora. Supongamos que se tiene un generador en el cual los valores de sus parámetros son: a = 5, c = 7, X0 = 4 y m = 8. El generador quedará de la siguiente manera: Xn+1 = (5 Xn + 7) mod 8 N Xn (5Xn+7)/8 Xn+1 1 4 27/8 3 2 3 22/8 6 3 6 37/8 5 4 5 32/8 0 5 0 7/8 7 6 7 42/8 2 7 2 17/8 1 8 1 12/8 4 Otros métodos para generar números pseudoaleatorio Algoritmo de Schrage Un algoritmo para multiplicar dos enteros de 32 bits y un 32-bits constante sin necesidad de utilizar ningún intermedios mayor de 32 bits. También es útil en ciertos tipos de generadores de números aleatorios. M = aq + r q = [M/a], r = M mod a Schrage: se utiliza q = 127773 y r = 2836 Generador lagged-fibonacci En los últimos años se ha convertido en un generador muy popular para maquinas tanto de procesamiento serial como paralelo. Su nombre se deriva de su familiaridad con la serie de Fibonacci.  X n =(X n-j  X n-k ) mod M donde j < k, M = 2 m   es cualquier operador binario Una de las ventajas de este generador consiste en que puede ser implementado directamente con números de punto flotante, y evitar la conversión de enteros a punto flotante que acompaña a otros generadores. Para la implementación de este generador es necesario almacenar una tabla con los previos k números. Generador de congruencia inversa No siendo ampliamente distribuido, un importante generador de números aleatorios es el método de la congruencia inversa, el cual viene dado por:  X n = a (X n-1 ) -1 + b Mod m donde X -1 denota el inverso multiplicativo, es decir X(X - 1 )=1  El periodo máximo es m. La escogencia de los parámetros iniciales es una de las principales ventajas del método, ya que no implica gran proceso. Una de las desventajas es que el costo de realizar el proceso del inverso modular es considerablemente alto en comparación con el método de congruencia lineal. Generador Shift-Register Existen dos formas para generar números aleatorios enteros a partir de la ecuación siguiente (∑ )( ) La primera, conocida como el método multi-step, toma n sucesivos bits de la ecuación para formar un entero de n bits, entonces, n bits adicionales son generados para crear el próximo entero. El segundo llamado el feedback shift-register, crea un nuevo entero pseudo aleatorio para cada iteración de la ecuación. Es decir, construye el número entero con el bit generado y los n-1 bits generados anteriormente; por lo tanto, un nuevo número aleatorio es generado por cada bit generado. Generador Xorshift Xorshift es un generador de números aleatorios, forma parte de una clase de generadores de números pseudo-aleatorios que fueron descubiertas por George Marsaglia. Ellos generan el siguiente número en la secuencia mediante la adopción de varias veces el exclusivo o de un número con un poco desplazado versión de sí mismo. Esto los hace extremadamente rápido en arquitecturas informáticas modernas. El cambio xor primitiva es invertible si el número de combinaciones es impar, pero no de lo contrario (la mayoría de las implementaciones xorshift libro de texto tienen 3 combinaciones, ya que este es el número mínimo para un generador período máximo, dado parámetros correctos). Ellos son una subclase de registros de desplazamiento con realimentación lineal, pero su implementación simple normalmente los hace más rápido y utiliza menos espacio. Sin embargo, los parámetros tienen que ser elegidos con mucho cuidado a fin de lograr un largo período. Bibliografía Rodríguez Torres, Federico, and Delgado Altamirano, Ricardo. Técnicas y modelos de simulación de sistemas. México: Instituto Politécnico Nacional, 1991. ProQuest ebrary. Web. 23 September 2014. Copyright © 1991. Instituto Politécnico Nacional. All rights reserved. Marquez, Carlos. Numeros Pseudoaleatorios. [Fecha de consulta: 22 de septiembre de 2014]. Disponible en: http://carlosmarquez.files.wordpress.com/2012/02/unidad-4- generacion-de-numeros-pseudoaleatorios1.pdf Mancilla, Alfonso. Números aleatorios. Universidad del norte, 2000. [Fecha de consulta: 21 de septiembre de 2014]. Disponible en: http://ciruelo.uninorte.edu.co/pdf/ingenieria_desarrollo/8/numeros_aleatorios.pdf Flesia, Georgina. Generadores de números pseudoaleatorio. Marzo de 2014[Fecha de consulta: 21 de septiembre de 2014]. Disponible en: http://www.famaf.unc.edu.ar/~flesia/MyS_2014/WEB/clase5_pr.pdf