Cualquier Cosa
Páginas: 6 (1330 palabras)
Publicado: 9 de mayo de 2012
Generación de secuencias de números aleatorios
Los números aleatorios son la base en los modelos de simulación donde hay variables estocásticas, ya que dichos números son la herramienta para generar eventos de tipo probabilístico.
Un paso clave en simulación es tener rutinas que generen variables aleatorias con distribuciones especificas: exponencial, normal, etc. Esto es hecho en dos fases.La primera consiste en generar una secuencia de números aleatorios distribuidos uniformemente entre 0 y 1. Luego esta secuencia es transformada para obtener los valores aleatorios de las distribuciones deseadas.
Generadores Congresiales Lineales
En 1951, D. H. Lehmer descubrió que residuos de potencias sucesivas de un número tienen buenas propiedades aleatorias:
Una expresión equivalentepara calcular Xn después de calcular Xn-1 es:
Los parámetros a y m son llamados multiplicador y modulo respectivamente. Muchos de los generadores actuales son generalizaciones de la propuesta de Lehmer y tienen la siguiente forma:
en donde los x son enteros entre 0 y m-1, y las constantes a y b son no-negativas. La selección de a, b, y m afectan el periodo y la autocorrelación enla secuencia. Entre los resultados de los estudios realizados con estos generadores tenemos:
1. El modulo m debe ser grande. Dado que los x están entre 0 y m-1, el periodo nunca puede ser mayor que m.
2. Para que el computo de mod m sea eficiente, m debe ser una potencia de 2, es decir, 2^k. En este caso mod m puede ser obtenido truncando el resultado y tomando en k bits a la derecha.
3. Sib es diferente de cero, el periodo máximo posible m se obtiene si y solo si:
a) Los enteros m y b son primos relativos -- no tengan factores comunes excepto el 1.
b) Todo número primo que sea un factor de m lo es también de a-1.
c) es un múltiplo de 4 si m es un múltiplo de 4.
Todas estas condiciones se cumplen si m = 2^k , a = 4c + 1, y b es impar, donde c, b, y k son enterospositivos. Si un generador tiene el periodo máximo posible se llama generador de periodo completo. Todos los generadores de periodo completo no son igualmente buenos. Son preferibles los generadores con menor autocorrelación entre números sucesivos. Por ejemplo, los dos generadores siguientes son de periodo completo, pero el primero tiene una correlación de 0.25 entre Xn-1 y Xn , mientras que el segundotiene una correlación despreciable de menos de 2^-18.
1. GCL multiplicativos
Los GCL presentados anteriormente son GCL mixtos. Si el incremento b es cero, no hay adición y el generador es llamado GCL multiplicativo y tienen la forma:
Es obvio que estos son más eficientes que los mixtos. Eficiencia adicional puede ser obtenida tomando m= 2^k . Por lo tanto hay dos tipos de GCLmultiplicativos dependiendo si m = 2^k o no.
2. GCL multiplicativos con m = 2^k .
El argumento a favor de usar m = 2^k esta en la eficiencia de la operación mod. Sin embargo estos generadores no son de periodo completo. El máximo periodo posible para estos generadores es un cuarto del periodo completo: 2^k-2 , y se obtiene si el multiplicador es de la forma 8i ± 3 y la semilla es impar. A pesar deesto, un cuarto de periodo máximo posible puede ser suficiente para muchas aplicaciones.
Ejemplo
Consideremos el siguiente GCL multiplicativo:
Si X0 = 1, obtenemos la secuencia 5, 25, 29, 17, 21, 9, 13, 1, 5, ..., con periodo 8 = 32/4. Si cambiamos X0 = 2, la secuencia es 2, 10, 18, 26, 2, 10,..., con periodo 4. Para ver qué sucede si el multiplicador no es de la forma 8i ± 3,consideremos:
Si x0 = 1, obtenemos la secuencia 1, 7, 17, 23, 1, 7, ..., y vemos que ambas condiciones son necesarias para obtener el periodo máximo.
Comprobación de las secuencias de números aleatorios
Tenemos que decidir si las secuencias generadas son lo suficientemente aleatorias como para poder ser utilizadas en nuestras aplicaciones. No podemos juzgar por nosotros mismos si una secuencia de...
Los números aleatorios son la base en los modelos de simulación donde hay variables estocásticas, ya que dichos números son la herramienta para generar eventos de tipo probabilístico.
Un paso clave en simulación es tener rutinas que generen variables aleatorias con distribuciones especificas: exponencial, normal, etc. Esto es hecho en dos fases.La primera consiste en generar una secuencia de números aleatorios distribuidos uniformemente entre 0 y 1. Luego esta secuencia es transformada para obtener los valores aleatorios de las distribuciones deseadas.
Generadores Congresiales Lineales
En 1951, D. H. Lehmer descubrió que residuos de potencias sucesivas de un número tienen buenas propiedades aleatorias:
Una expresión equivalentepara calcular Xn después de calcular Xn-1 es:
Los parámetros a y m son llamados multiplicador y modulo respectivamente. Muchos de los generadores actuales son generalizaciones de la propuesta de Lehmer y tienen la siguiente forma:
en donde los x son enteros entre 0 y m-1, y las constantes a y b son no-negativas. La selección de a, b, y m afectan el periodo y la autocorrelación enla secuencia. Entre los resultados de los estudios realizados con estos generadores tenemos:
1. El modulo m debe ser grande. Dado que los x están entre 0 y m-1, el periodo nunca puede ser mayor que m.
2. Para que el computo de mod m sea eficiente, m debe ser una potencia de 2, es decir, 2^k. En este caso mod m puede ser obtenido truncando el resultado y tomando en k bits a la derecha.
3. Sib es diferente de cero, el periodo máximo posible m se obtiene si y solo si:
a) Los enteros m y b son primos relativos -- no tengan factores comunes excepto el 1.
b) Todo número primo que sea un factor de m lo es también de a-1.
c) es un múltiplo de 4 si m es un múltiplo de 4.
Todas estas condiciones se cumplen si m = 2^k , a = 4c + 1, y b es impar, donde c, b, y k son enterospositivos. Si un generador tiene el periodo máximo posible se llama generador de periodo completo. Todos los generadores de periodo completo no son igualmente buenos. Son preferibles los generadores con menor autocorrelación entre números sucesivos. Por ejemplo, los dos generadores siguientes son de periodo completo, pero el primero tiene una correlación de 0.25 entre Xn-1 y Xn , mientras que el segundotiene una correlación despreciable de menos de 2^-18.
1. GCL multiplicativos
Los GCL presentados anteriormente son GCL mixtos. Si el incremento b es cero, no hay adición y el generador es llamado GCL multiplicativo y tienen la forma:
Es obvio que estos son más eficientes que los mixtos. Eficiencia adicional puede ser obtenida tomando m= 2^k . Por lo tanto hay dos tipos de GCLmultiplicativos dependiendo si m = 2^k o no.
2. GCL multiplicativos con m = 2^k .
El argumento a favor de usar m = 2^k esta en la eficiencia de la operación mod. Sin embargo estos generadores no son de periodo completo. El máximo periodo posible para estos generadores es un cuarto del periodo completo: 2^k-2 , y se obtiene si el multiplicador es de la forma 8i ± 3 y la semilla es impar. A pesar deesto, un cuarto de periodo máximo posible puede ser suficiente para muchas aplicaciones.
Ejemplo
Consideremos el siguiente GCL multiplicativo:
Si X0 = 1, obtenemos la secuencia 5, 25, 29, 17, 21, 9, 13, 1, 5, ..., con periodo 8 = 32/4. Si cambiamos X0 = 2, la secuencia es 2, 10, 18, 26, 2, 10,..., con periodo 4. Para ver qué sucede si el multiplicador no es de la forma 8i ± 3,consideremos:
Si x0 = 1, obtenemos la secuencia 1, 7, 17, 23, 1, 7, ..., y vemos que ambas condiciones son necesarias para obtener el periodo máximo.
Comprobación de las secuencias de números aleatorios
Tenemos que decidir si las secuencias generadas son lo suficientemente aleatorias como para poder ser utilizadas en nuestras aplicaciones. No podemos juzgar por nosotros mismos si una secuencia de...
Leer documento completo
Regístrate para leer el documento completo.