generadores

Universidad de El Salvador
Facultad Multidisciplinaria Orienta
Departamento de CC.NN y Matemáticas
Sección de Matemática.



Generador de Congruencia lineales.


El generador de Congruencia Lineal (abreviado como GCL) es uno de los tipos más simples de generadores de números aleatorios, con números aleatorios obtenidos entre 0 y 1, en los que se da por la relación modular derecurrencia.

Una gran mayoría de los generadores utilizados actualmente utilizan esta técnica introducida por Lehmer en 1951. Una secuencia de números enteros Z1,Z2, . . . está definida por la fórmula recursiva:

Zi = (aZi−1 + c) mod m


Donde el módulo m, el multiplicador a, el incremento c y la semilla o valor de comienzo Z0 son enteros no negativos.

Evidentemente, por definición, severifica que:

0 _ Zi < m

Para obtener un número aleatorio de la distribución uniforme [0,1) se debe hacer Ui =Zi/m

Además de ser no negativos se debe verificar que:
0 < m, a < m, c < m, Z0 < m
Es decir :




Por lo tanto, la primera objeción que se le puede hacer a este método, objeción común a todos los generadores de números aleatorios, es que la sucesión de los valores Zi no es enabsoluto aleatoria. Sin embargo, posteriormente veremos que si elegimos las parámetros iniciales convenientemente, la sucesión puede asemejarse a una sucesión de numeros aleatorios.

Otra objeción a realizar es que los números Ui solo pueden tomar valores, por tanto la probabilidad de obtener un valor de Ui entre 0,1/m y 0,9/m es 0 cuando debiera ser 0, 8/m > 0. Ahora bien, si se elige un msuficientemente grande los puntos en el intervalo [0,1) serán muy densos, ya que si elegimos un m≥109 hay como mínimo mil millones de valores posibles para Ui espaciados todos la misma distancia. Se considera que esto es una aproximación lo suficientemente buena para la mayoría de los planteamientos.

Dada la forma de la expresión Zi es inevitable el comportamiento como un bucle,
es decir, que enel momento que se repita un Zi todos los siguentes serán iguales a los obtenidos hasta ese momento. La longitud de cada uno de esos ciclos se conoce como periodo del generador y se representa por p. Como Zi solo depende de Zi−1 y se verifica que 0 ≤Zi ≤m - 1 es claro que p ≤m. Si p = m el generador se llama de periodo total.

A continuación Mostraremos un ejemplo para mayor entendimiento:Sea m = 16, a = 5, c = 3 y Z0 = 7, la secuencia de los Zi obtenidos será:
Zi = (5Zi−1 + 3) mod 16



Y haciendo Ui =Zi/m se tiene el siguiente recuadro:



De los ejemplos anteriores se desprende que una cuestión de interés es como elegir los parámetros del generador de forma que este tenga ciclo completo. El siguiente teorema, propuesto por Hull yDobell (1962) proporciona un caracterización en este sentido.
Un generador congruencia tiene periodo completo si y solo si se cumplen
las siguientes condiciones:
1. m y c son primos entre si
2. Si q es un numero primo que divide a m, entonces q divide a a-1.
3. Si 4 divide a m, entonces 4 divide a a- 1.


Generador Combinatorio


Es posible combinar generadores para obtener “mejores”generadores. Algunas de las técnicas usadas son:

OR-exclusivo de números aleatorios de dos o más generadores. Esta técnica es similar a la anterior excepto que la suma es reemplazada por un or-exclusivo bit por bit. Se ha demostrado que esta técnica aplicada a números ligeramente aleatorios puede ser usada para generar números con mayor aleatoriedad.

Barajeo. Usa una secuencia como un índice paradecidir que número generado por otra secuencia será retornado. Por ejemplo, uno de estos algoritmos usa un arreglo de tamaño 100 que contiene números de una secuencia aleatoria xn . Para generar un número aleatorio se genera un número aleatorio yn (entre 0 y m-1) para obtener el índice i = 1 + 99yn / (m-1). El valor del i-esimo elemento del arreglo es devuelto. Un nuevo valor xn es calculado y...