Generadores Aleatorios

INTRODUCCION

Un generador de números aleatorios es un dispositivo informático o físico diseñado para producir secuencias de números sin un orden aparente.

Actualmente existen diferentes tipos de generadores de números aleatorios, que, casi siempre, son descritos por libros de simulación. Los generadores de números aleatorios generalmente se extienden a muchas aplicaciones de computadoras, tales como experimentos estadísticos, juegos de ordenador, criptografía, protocolos de seguridad, entre otros.

En el presente documento informativo, se expondrá un tema de mucha relevancia en la probabilidad, el cual tratara de resumir en una forma breve y concisa los principales generadores de números aleatorios que existen hasta el momento, mostrando sus características más notables, sus ventajas y desventajas, además de tratar de ejemplificar cada una de ellas de la manera más factible posible.

Resumen:

Generadores de Números Aleatorios.

Un generador de números aleatorios es un dispositivo informático o físico diseñado para producir secuencias de números sin un orden aparente.

Las principales ventajas de los generadores de numeros aleatorios son:

- Rapidez

- Comodidad

- Reproducibilidad

- Portabilidad

Y la desventaja fundamental:

- Las secuencias obtenidas no son realmente aleatorias, ya que se obtienen con operaciones deterministas. Solo podemos obtener secuencias pseudo-aleatorias, que a su vez satisfacen algunos criterios de aleatoriedad adecuados.

Existen varios tipos de generadores de números aleatorios. Los principales son:

Generador de Fibonacci extendido

Generador Combinatorio

Generador de Congruencia lineales.

Además de estos se encuentran otros generadores:

Generador de los cuadrados medios

Generador de Cuadrados centrales

Entre otros

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 de recurrencia.

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, se verifica 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 en absoluto 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 m suficientemente 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 en el 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 y Dobell (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.

...