Generar Números Aleatorios con Métodos Congruenciales

En los experimentos de simulación es necesario generar números aleatorios que representen alguna distribución de probabilidad. Para tal propósito tenemos que generar números rectangulares. Ahora bien, si esos números son generados a través de reglas determinísticas ¿acaso no sería más preciso llamarles números pseudoaleatorios? De hecho, pero bien podríamos mirar desde el otro lado de la calle y decir que “una sucesión cumple la facultad de aleatoria si satisface las pruebas estadísticas de aleatoriedad”

Métodos Congruenciales

Los generadores de números aleatorios que más se usan son los generadores congruenciales lineales (LCG) ideados por un tal Lehmer. El chiste de un LCG es generar un valor aleatorio a partir de otro anterior. En este post estudiaremos los dos métodos congruenciales lineales más populares:

Congruencial Mixto

La fórmula (o relación de recurrencia) es sencilla:

X_{n + 1} = (aX_n + c) \mod{m}

Donde:

  • X0 es la semilla
  • a el multiplicador
  • c la constante aditiva y
  • m el módulo

A tener en cuenta: Los valores a, X0 y c tienen que ser mayores que cero. Y la variable m tiene que ser mayor que las tres anteriores. Para entrar en acción vamos a darle valores arbitrarios a cada uno de estos parámetros y estudiar que reacción tienen en la relación de recurrencia. Supongamos que a = 5, c = 7, X0 = 7 y m = 8. Entonces los resultados son:

n Xn Xn + 1
0 7 2
1 2 1
2 1 4
3 4 3
4 3 6
5 6 5
6 5 0
7 0 7

Nótese que después de 8 pasadas el valor inicial de X se repite. Decimos entonces que el periodo del generador es 8… igualito al valor del módulo… Eso no siempre es así. Veamos un caso donde el periodo es menor a m. El valor de los parámetros es a = c = X0 = 4 y m = 6. Ahora lo resultados son:

n Xn Xn + 1
0 4 6
1 6 0
2 0 4

Para que la cosa tome más sabor, a continuación un script en Python que genera números aleatorios implementando el generador congruencial lineal mixto:

def mixedMethod(x, a, c, mod):

    periodo = 0
    bandera = 0

    while(bandera != x):
        if (periodo == 0):
            bandera = x
        x = (a * x + c) % mod
        print(x)
        periodo = periodo + 1

    if(periodo == mod):
        print("El periodo es completo: ", periodo)
    else:
        print("El periodo es incompleto:", periodo)

def main():
    x = int(raw_input("Introduce el valor de la semilla: "))
    a = int(raw_input("Introduce el valor del multiplicador: "))
    c = int(raw_input("Introduce el valor de la constante aditiva: "))
    m = int(raw_input("Introduce el valor del modulo: "))
    mixedMethod(x,a,c,m)

if __name__ == "__main__":
    main()

Actualización:Aquí una versión en C# (en inglés)

Congruencial Multiplicativo

El generador congruencial lineal multiplicativo es básicamente el mismo rollo. La relación de recurrencia es similar a la del método anterior:

X_{n + 1} = (aX_n) \mod{m}

Incluso sólo cambiaríamos una línea del código:

         x = (a * x + c) % mod

La información la saqué del libro Simulación: Un enfoqué práctico de Raúl Coss Bu. Por ahora es todo. Woo-Hoo!