UNIDAD II: NÚMEROS PSEUDO ALEATORIOS

2.1 LOS NÚMEROS PSEUDO ALEATORIOS 

Para poder realizar una simulación que incluya variabilidad dentro de sus eventos, es preciso generar una serie de números que sean aleatorios por sí mismos, y que su aleatoriedad se extrapole al modelo de simulación que se esta construyendo.

Unas de las primeras tareas que es necesario llevar a cabo consiste en determinar si los números que utilizaremos para "correr" o ejecutar la simulación son realmente aleatorios o no; por desgracia, precisar lo anterior con absoluta certidumbre resulta muy complicado, ya que para ello tendríamos que generar un número infinito de valores que nos permitiera comprobar la inexistencia de correlaciones entre ellos.

A pesar de lo anterior, podemos asegurar con altos niveles de confiabilidad que el conjunto de números que utilizaremos en una simulación se comportan de manera muy similar a un conjunto de números totalmente aleatorios; por ello es que se les denomina números pseudo aleatorios. Casi todas las aplicaciones comerciales tienen varios generadores de números pseudo aleatorios que pueden generar un conjunto muy de números sin mostrar correlación entre ellos.

2.2 GENERACIÓN DE NÚMEROS PSEUDO ALEATORIOS

Para realizar una simulación se requieren números aleatorios en el intervalo (0,1), a los cuales se hará referencia como ri, es decir, una secuencia ri=(r1, r2, r3,…,rn) que contiene n números, todos ellos diferentes; n recibe el nombre de periodo o ciclo de vida del generador que creó la secuencia ri.

Los ri constituyen la parte medular de la simulación de procesos estocásticos y generalmente se usan para generar el comportamiento de variables aleatorias, tanto continúas como discretas. Debido a que no es posible generar números realmente aleatorios, consideramos los ri como números pseudo aleatorios, generados por medio de algoritmos determinísticos que requieren parámetros de arranque.

De acuerdo con L´Ecuyer una secuencia ri con periodo de vida n=2*31=2,147,483,648 es relativamente pequeña; de hecho, incluso una secuencia de ri que contenga un ciclo de vida n=2*64 se considera pequeña.

A continuación se mostrara la razón de por qué se requiere una secuencia de números ri suficientemente grande.

Suponga que queremos simular el tiempo de atención a clientes en un banco que tiene 5 cajeros en paralelo, cada uno de los cuales atiende aproximadamente 50 clientes diarios. Para simular el tiempo de atención se requiere un generador de variable aleatoria en función de ri, por ejemplo Ti=5+2ri, expresado minutos para toda i=1, 2,3,…,n. simulamos el tiempo de atención de manera aislada, es decir, sin considerar el tiempo transcurrido desde la llegada de éstos, serán necesarios 5x50=250 números ri para simular un día; si deseáramos simular 5 días se necesitarían 2150x5=1250ri para simular el tiempo transcurrido desde la llegada al banco de los 250 clientes por día y 250x5=1250ri para simular el correspondiente al total de clientes atendidos durante 5 días. Por lo tanto se requerirían 2,500 números pseudo aleatorios ri para simular la operación del banco durante 5 días.

Los resultados no pueden basarse en una sola simulación del sistema; por el contrario, es necesario realizar varias réplicas de la misma, corriendo cada una de ellas con números pseudo aleatorios diferentes. Retomando el ejemplo del banco, simular 5 días otra vez significa que necesitamos otros 2,500 números pseudo aleatorios den el intervalo (0,1). Se requerirían 5,000 ri para realizar la simulación del sistema con dos réplicas.

Una vez generado el conjunto ri mediante un algoritmo determinístico, es necesario someterlo a pruebas para verificar su los números son realmente independientes y uniformes; si las supera, podrá utilizarse en el simulación; de lo contrario, simplemente deberemos desecharlo.

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

Lo difícil es diseñar un algoritmo que genere un conjunto de ri con periodo de vida suficientemente grande (N) y que supere las pruebas de uniformidad e independencia; lo cual implica evitar:

·         Que los números de conjunto ri no estén uniformemente distribuidos, es decir, que haya demasiados ri en un subintervalo y en otro muy pocos o ninguno.

·         Que los números ri generados sean discretos en lugar de continuos.

·         Que la media del conjunto sea muy alta o muy baja, es decir, que esté por arriba o por debajo del ½.

·         Que la varianza del conjunto sea muy alta o muy baja, es decir, que se localice por arriba o por debajo del 1/12.

2.2.1 Algoritmos de Cuadrados medios

Este algoritmo 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. Este método se repite hasta obtener n números r_i. 

• 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_i 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.
• 5.    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:

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

Solución:

Y₀=(5735)²=32890225

Y₁=(8902)²=79245604

Y₂=(2456)²=06031936

Y₃=(0319)²=101 761

Y₄=(0176)²= 030976

X₁ = 8 902

X₂ = 2 456

X₃ = 0319

X₄ = 0176

X₅ = 3 097

r₁ = 0.8902

r₂ = 0.2456

r₃ = 0.0319

r₄ = 0.0176

r₅ = 0.3097

El algoritmo de cuadrados medios generalmente es incapaz de generar una secuencia de r_i con periodo de vida n grande. Además, en ocasiones sólo es capaz de generar un número, por ejemplo, si X₀ = 1000, entonces X₁ = 0000; r_i = 0.000 y se dice que el algoritmo se degenera  con la semilla de X₀ = 1 000.

2.2.2 Algoritmos de Productos Medios

La mecánica de generar números pseudo aleatorios de este algoritmo no congruencial se define de la siguiente manera:

• Se requiere de dos números semillas, ambas con D dígitos
• Las semillas se multiplican y del producto se seleccionan los D dígitos del centro aquí se forma el primer número pseudo aleatorio r_i=0
• 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 el segundo número r_i.
• Se elimina la segunda semilla y se multiplican el primer número de D dígitos por el segundo número de D dígitos; de este 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.

Nota: si no es posible obtener los D dígitos del centro agregue números a la izquierda del mismo.

Ejemplo

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

Solución:

Y₀= (5015) (5734) = 28 756 010   X₂=7560   r₁= 0.7560

Y₁= (5734) (7560) = 43 349 040   X₃= 3490  r₂=0.3490

Y₂= (7560) (3490) = 26 384 400   X₄= 3844   r₃=0.3844

Y₃= (3490) (3844) = 13 415 560   X₅= 4155   r₄= 0.4155

Y₄= (3844) (4155) = 15 971 820   X₆= 9718   r₅=0.9718

2.2.3 Algoritmo del multiplicador constante

Este algoritmo no congruencia es similar al algoritmo de productos medios. Los pasos necesarios para generar un número pseudoaleaotoria con este algoritmo son:

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

2.       Seleccionar una constante (a ) con D dígitos (D>3)

3.       Sea y₀=a*X₀; sea X₁= los D dígitos del centro y sea ri=0. D dígitos del centro

4.       Sea yi=a*Xi; sea Xi+1= los D dígitos del centro, y sea ri+1=0. D dígitos del centro para toda i= 1, 2, 3, …, n

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

2.2.4 Algoritmo lineal

Este algoritmo congruencial fue propuesto por D. H. Lehmer en 1951. Según Law y Kelton, este algoritmo ha sido el más usado. El algoritmo congruencial lineal genera una secuencia de números enteros por medio de la siguiente ecuación recursiva:

Xᵢ₊₁=(aXᵢ+c)mod(m)           i=0,1,2,3,…,n

Donde X0= Semilla

A= Constante multiplicativa

C= Constante aditiva

M= Modulo

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ᵢ₊₁=(aXᵢ)mod(m)        i=0,1,2, 3,…,n

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ᵍ

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

K=0,1,2,3…

X0 debe ser un número impar

G debe sr entero

2.2.6 Algoritmo congruencial aditivo

En este algoritmo requiere una secuencia previa de n números enteros X1, X2, X3, X4,…, Xn para generar una nueva secuencia de números enteros que empiezan en Xn+1, Xn+2, Xn+3, Xn+4,…, Xn+n.

Su ecuación recursiva es:

Xᵢ= (Xᵢ₋₁+Xᵢ₋n)mod(m)      i=n+1, n+2, n+3,…,N

2.2.7 Algoritmos congruenciales no 

lineales

Se analizan dos algoritmos congruenciales no lineales:

·         Algoritmo congruencial dramático: Este algoritmo tiene la siguiente ecuación recursiva

Xi+1=(aX²ᵢ+bXᵢ+c)mod(m)        i=0,1,2,3,…,N

En este caso os números rᵢ, pueden ser generados por: rᵢ=Xᵢ/(m-1)

M=2ᵍ

A debe ser un numero par

C debe ser número impar

G debe ser numero entero

(b-1) mod=4

·         Algoritmo de Blum, Blum y Shub

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

X²ᵢ)mod(m)   i=0,1,2,3,…,n

Link de ejercios: https://drive.google.com/open?id=0B9XIpzwZmrNRWjNrLU1WZUxNa28

BIBLIOGRAFIA:

García. E., García. H., Cárdenas. L. (2006), Simulacoón y análisis de sistemas con Promodel, México, PEARSON Educación.