Capítulo 2: "NÚMEROS PSEUDO ALEATORIOS"

2.1 Los Números Pseudo aleatorios

Se le llama así a la serie de números aleatorios o al azar que se generan para poder realizar una simulación e incluyendo una variabilidad dentro de sus eventos, a partir de su aleatoriedad nos ayudará a obtener conclusiones dentro del modelo de simulación que estemos construyendo.

Se le denominan números pseudo aleatorios porque nos dan esa confiabilidad de que el conjunto de números que usemos en el modelo de simulación se comportarán de igual manera a los números totalmente aleatorios que utilicemos para representar el valor que tomará alguna variable.

Existen varios generadores de números pseudo aleatorios, en aplicaciones comerciales, por ejemplo, que pueden generar un conjunto muy grande de números sin mostrar correlación entre ellos.

2.2. Generación de números pseudo aleatorios.

Para realizar una simulación son necesarios números aleatorios en el intervalo (0,1), a los cuales se hará referencia como r_i, es decir una secuencia r_i = {r₁,r₂,r₃,…, r_n} que contiene n números, todos ellos diferentes; n recibe el nombre de periodo o ciclo de vida del generador que creó la secuencia r_i.

r_i constituye la parte medular de la simulación de variables aleatorias de procesos estocásticos. Se usan para generar el comportamiento de variables aleatorias, tanto continuas como discretas.

No es posible generar números realmente aleatorios, se considera los r_i como números pseudo aleatorios, generados por medio de logaritmos determinísticos que requieren parámetros de arranque. Es necesario contar con un conjunto suficientemente grande de r_i para simular el comportamiento de una o más variables aleatorias.

Dada la importancia de contar con un conjunto de r_i, suficientemente grande, en esta sección se presentan diferentes algoritmos determinísticos para obtenerlo. Por otra parte, es conveniente señalar que el conjunto de r_i debe ser sometido a una variedad de pruebas para verificar si los números que lo conforman son realmente independientes y uniformes. Una vez generado el conjunto r_i mediante un algoritmo determinístico, es necesario someterlo a las pruebas antes mencionadas: si las supieras, podrá utilizarse en la simulación, de lo contrario, simplemente se debe desechar.

Un conjunto de r debe seguir una distribución uniforme continua, la cual está definida por:

Generar un conjunto de r_i es una tarea sencilla, para ello, se tiene que diseñar un propio algoritmo de generación. Lo que es difícil es diseñar un algoritmo que genere un conjunto de r_i con periodo de vida suficientemente grande (N) y que además pase sin problema las pruebas de uniformidad e independencia, lo cual implica evitar problemas como:

• Que los números del conjunto r no estén uniformemente distribuidos, es decir, que haya demasiados r en un subintervalo y en otro muy pocos o ninguno.
• Que los números r generados sean discretos en lugar de continuos.
• Que la medida del conjunto sea muy alta o muy baja, es decir, que se localice por arriba o por debajo del ½

En ocasiones también se presentan anomalía como números r_i seguidos por arriba o por debajo de la media, secuencia de r_i por arriba de la media, seguida de una secuencia por debajo de la media y viceversa, o varios r_i seguidos en forma ascendente o descendente.

2.2.1 Algoritmo de cuadrados medios 

Este algoritmo no congruencial fue propuesto en la década de los cuarenta del siglo xx por Von Neumann y Metropolis. Requiere un número entero detonador (llamado semilla) con D dígitos, el cual es elevado al cuadrado para seleccionar del resultado los D dígitos del centro; el primer número r_i se determina simplemente anteponiendo el “0” a esos dígitos. Para obtener el segundo r_i se sigue el mismo procedimiento, sólo que ahora se elevan al cuadrado los D dígitos del centro que se seleccionaron para obtener el primer r_i. Este método se repite hasta obtener n números r_i. A continuación se presentan con más detalle los pasos para generar números con el algoritmo de cuadrados medios.

1. Seleccionar una semilla (X₀) con D dígitos (D>3).

2.- Sea X₀= resultado de elevar X₀ al cuadrado; sea X₁= los D dígitos del centro, y sea r_i=0. D dígitos del centro.

3. Sea Y_i = resultado de elevar X₁ al cuadrado; sea X_i+1= los D dígitos del centro, y sea r_i=0. D dígitos del centro para toda i= 1,2,3,…,n.

4. Repetir el paso 3 hasta obtener los n números r_i deseados.

Nota: Si no es posible obtener los D dígitos del centro del número Y_i, agregue ceros a la izquierda del número Y_i.

Ejemplo 2.1 

Generar los primeros 5 números r_i a partir de las semillas X₀=5 735; observe que ambas semillas tienen D= 4 dígitos.

Ejemplo 2.1.xlsx

Explicación 2.2.1.docx

2.2.2 Algoritmo de productos medios

La mecánica de generación de números pseudo aleatorios de este algoritmo no congruencial es similar a la del algoritmo de cuadrados medios. La diferencia entre ambos radica en que el algoritmo de productos medios requiere dos semillas, ambas con D dígitos; además, en lugar de elevarlas al cuadrado, las semillas se multiplican y del producto se seleccionan los D dígitos del centro, los cuales formarán el primer número pseudo aleatorio r_i=0. D dígitos. Después se elimina una semilla, y la otra se multiplica por el primer número de D dígitos, para luego seleccionar del producto los D dígitos que conformaran un segundo número r_i. Entonces se elimina la segunda semillas y se multiplican el primer número de D dígitos por el segundo número de D dígitos; del producto se obtiene el tercer número r_i. Siempre se ira eliminando el número más antiguo, y el procedimiento se repetirá hasta generar los n números pseudo aleatorios. A continuación se presentan con más detalle los pasos del método para generar números con el algoritmo de productos medios.

1. Seleccionar una semilla (X₀) con D dígitos (D>3).

2. Seleccionar una semilla (X₁) con D dígitos (D>3).

3. Sea Y₀= X₀* X₁; sea X₂= los D digitos del centro, y sea r_i=0. D dígitos del centro.

4. Sea Y₁= X_i *X_i+1; sea X_i+2= los D digitos del centro, y sea r_i+1=0. D dígitos del centro para toda i= 1, 2,3,…, n.

5. Repetir el paso 4 hasta obtener los números r_i deseados.

Nota: Si no es posible obtener los D dígitos del centro del número Y_i, agregue ceros a la izquierda del número Y_i.

Ejemplo 2.2

Generar los primeros 5 números r_i a partir de las semillas X₀=5 015 y X₁=5 734; observe que ambas semillas tienen D= 4 dígitos.

Ejemplo 2.2.xlsx

Explicación 2.2.2.docx

2.2.3. Algoritmo de multiplicador constante

El algoritmo no congruencial es similar al algoritmo de productos medios.

     Los pasos necesarios para generar números pseudo aleatorios con el algoritmo de multiplicador constante son:

• Seleccionar una semilla (X₀) con D dígitos (D >3).
• Seleccionar una constante (a) con D dígitos (D > 3).
• Sea Y=(a*X₀), sea X₁= los D dígitos del centro, y sea r_i=0.D dígitos del centro.
• Sea Y=(a*X_i), sea X_i+1= los D dígitos del centro, y sea r_i+1=0.D dígitos del centro para toda i=1, 2, 3, …, n.
• Repetir el paso 4 hasta obtener los n números r_i deseados.

Ejemplo 2.3

Generar los primeros 5 números r_i a partir de la semilla X₀= 9803 y con la constante a = 6965. Observe que tanto la semilla como la constate tienen D = 4 dígitos.

Generador de números aleatorios algoritmo de multiplicador constante.xlsx

 2.2.4. Algoritmo lineal

Este algoritmo fue propuesto por D.H. Lehmer en 1951. El algoritmo congruencial lineal genera una secuencia de números enteros por medio de la siguiente ecuación recursiva:

X_i+1 = (aX_i + C) mod (m)                   i = 0, 1, 2, 3, …, n.

Donde X₀ es la semilla, a es la constante multiplicativa, c es una constante aditiva y m es el módulo; X₀ >0, a>0, c>0 y m>0 deben ser números enteros. La operación mod (m) significa multiplicar X_i por a, sumar c y dividir el resultado entre m para obtener el residuo X_i+1. La ecuación recursiva del algoritmo congruencia lineal genera una secuencia de números enteros S= {0, 1, 2, 3, …, m-1}, y que para obtener números pseudo aleatorios en el intervalo (0,1) se requiere la siguiente ecuación:

r_i =            i-1, 2, 3, …, n

Ejemplo 2.5

Generar suficientes números entre 0 y 1 con los parámetros X₀=6, k=3, g=3 y c=7, hasta encontrar el periodo de vida máximo (N).

Generador de números aleatorios algoritmo lineal.xlsx

2.2.5 Algoritmo congruencial multiplicativo

El algoritmo congruencial multiplicativo surge del algoritmo congruencial lineal cuando c = 0. Entonces la ecuación recursiva es:

X_i+1 = (aX_i) mod (m)                    i = 0, 1, 2, 3,…, n

En comparación con el algoritmo congruencial lineal, la ventaja del algoritmo multiplicativo es que implica una operación menos a realizar. Los parámetros de arranque de este algoritmo son X₀, a y m, todos los cuales deben ser números enteros y mayores que cero. Para transformar los números X_i  en el intervalo (0,1) se usa la ecuación r_i = X_i / (m – 1). De acuerdo con Banks, Carson, Nelson y Nicol, las condiciones que deben cumplir los parámetros para que el algoritmo congruencial multiplicativo alcance su máximo periodo son:

                 m = 2^g

                       a = 3 + 8k o a = 5 + 8k

                 k = 0,1, 2, 3,…

                 X₀ debe ser un número impar

                 g debe ser entero

A partir de estas condiciones se logra un periodo de vida máximo N = k/4 = 2^g-2

Ejemplo 2.7 

Generar suficientes números entre 0 y 1 con los siguientes parámetros: X₀ = 17, k = 2 y g = 5, hasta encontrar el periodo o ciclo de vida.

Generador de números aleatorios algoritmo congruencial multiplicativo.xlsx

2.6 Algoritmo congruencial aditivo

 Este algoritmo requiere una secuencia previa de n números enteros X₁, X₂, X₃, X₄, …, X_n para generar una nueva secuencia de números enteros que empieza en X_n+1, X_n+2, X_n+3, X_n+4,…

Su ecuación recursiva es:

           X_i = (X_i+1 + X_i+n) mod (m)                  i = n + 1, n + 2, n + 3,…, N

Los números r_i pueden ser generados mediante la ecuación:

r_i = x_i / (m -1)

Ejemplo 2.9 

Generar 7 números pseudo aleatorios entre cero y uno a partir de la siguiente secuencia de números enteros: 65, 89, 98, 03, 69; m = 100.

Sean x₁ = 65, X₂ = 89, X₃ =98, X₄ = 03, X₅ = 69. Para generar r₁, r₂, r₃, r₄, r₅, r₆, r₇ antes es necesario generar  X₆, X₇, X₈, X₉, X₁₀, X₁₁, X_12.

Generador de números aleatorios algoritmo congruencial aditivo.xlsx

2.2.7 Algoritmos congruenciales no lineales 

       2.2.7.1 Algoritmo congruencial cuadrático

Este algoritmo tiene la siguiente ecuación recursiva

X_i+1 = (ax_i² + bx_i + c) mod (m)

i = 0, 1, 2, 3, …, N

Los números r, pueden ser generados con la ecuación:

r_i = x_i / (m - 1)

De acuerdo con L’Ecuyer, las condiciones deben cumplir los parámetros m, a, b y c, para alcanzar un periodo máximo de N = m son:

            m = 2^g

            a = debe ser un número par

            c = debe ser un número impar

           g = debe ser entero

           (b - 1)mod 4 = 1

De esta manera se logra un periodo de vida máximo N = m

 Ejemplo 2.10

Generar, a partir del algoritmo congruencial cuadrático, suficientes números enteros hasta alcanzar el periodo de vida, considerando los parámetros X₀ = 13, m = 8, a = 26, b = 27 y c = 27. Como todas las condiciones estipuladas para los parámetros se satisfacen, es de esperarse que el periodo de vida del generador sea N = m = 8, tal como podrá comprobar al revisar los cálculos correspondientes, que se presentan a continuación.

Generador de números aleatorios algoritmo congruencial no lineales.xlsx

   2.2.7.2 Algoritmo de Blum, Blum Shub

Si en el algoritmo congruencial cuadrático a = 1, b = 0 y c = 0, entonces se construye una nueva ecuación recursiva:

Esta ecuación fue propuesta por Blum, Blum Shub, (de ahí el nombre), como un nuevo método para generar números que no tienen un comportamiento predecible.

Bibliografía: 

Simulación y análisis de los sistemas con Promodel, García Dunna Eduardo, García Reyes Heriberto, Cárdenas Barrón Leopoldo E. Editorial: Pearson.