NÚMEROS PSEUDO ALEATORIOS

2.- GENERACION DE NUMEROS ALEATORIOS

2.1  NUMEROS ALEATORIOS

           

 Los números aleatorios son numeros que deben de cumplir los requisitos de espacio equiprobable, es decir, que todo elemento tenga la misma probabilidad de ser elegido y que la elección de uno no dependa de la elección del otro. Son generados por medio de una función determinista (no aleatoria) y que aparentan ser aleatorios.

Generadores de números aleatorios

Los métodos para generar números aleatorios involucran algún proceso físico cuasialeatorio, que genera sucesiones de números aleatorios de determinada longitud. El requisito general para las sucesiones es la independencia estadística. Para esto, existen varios métodos:

• Métodos manuales: Dispositivos mecánicos o electrónicos, lanzamientos de monedas o dados, empleo de barajas, ruletas. Son menos prácticos pero simples, lentos, atractivos, pedagógico.   Pero no  pueden reproducirse.
• Tablas de bibliotecas: Generados por los métodos anteriores. Están en tablas. Siempre pueden reproducirse, pero es un sistema lento.  Determinados problemas requieren  más números aleatorios que los publicados.
• Métodos de computación analógica: Dependen de procesos físicos aleatorios, por ejemplo: el ruido térmico de un circuito con  semiconductores, que convertido en un número binario, representa un valor numérico aleatorio. Se considera que conducen a verdaderos números aleatorios.
• Métodos de computación digital: Se han sugerido tres métodos para producir números aleatorios cuando se usan computadoras digitales; provisión externa, generación interna, relación de recurrencia.

           

Existen en la actualidad técnicas para generar con una computadora, variables aleatorias uniformemente distribuidas, r (en donde r  ≥  0 y   1  ≥  r). Los números generados por estas subrutinas de computadora se denominan números pseudoaleatorios, porque se generan a partir de una fórmula totalmente determinística mediante la computación. Sus propiedades estadísticas, coinciden con las de los números generados a través de un dispositivo fortuito idealizado que selecciona números de un intervalo unitario (0,1) de un modo independiente en donde son igualmente probables todos los números.

 A condición de que estos números pseudo aleatorios puedan pasar el conjunto de pruebas estadísticas (las de frecuencia, auto correlación, producto rezagado, corridas, de distancia y así sucesivamente) implicadas por un dispositivo fortuito idealizado, tales números pseudo aleatorios se pueden tratar corno si "en realidad lo fueran" a pesar de que no lo son.

Comparativa de métodos de generación

MÉTODOS	VENTAJAS	DESVENTAJAS
Manuales	Facil generación	Lentos, simples y poco prácticos
Tablas	Fácil implementación	Lentos y no reproducibles
Comp Analógica	Rápidos  “ verdaderos”	No reproducibles
Comp Digital	Rápidos	No son verdaderos

Requisitos para un buen generador de números pseudo aleatorios con distribución uniforme:

• La distribución de los números debe ser uniforme en todo el intervalo [0,1].
• Los  números deben ser independientes dentro de toda la serie generada.
• El ciclo del generador debe ser lo suficientemente grande.
• La serie debe volverse a repetir.
• Capaz de generar números pseudo aleatorios a altas velocidades.
• Requerir una mínima cantidad de la capacidad de memoria de Computador

Ejemplos de aplicación

• Simulación: La reproducción de fenómenos naturales necesita números aleatorios. En Física los ejemplos clásicos: Física Estadística, Física de Partículas
• Muestreo: Muchas veces es poco práctico examinar todos los casos posibles. Un muestreo aleatorio puede revelar un comportamiento típico.
• Análisis Numérico: Técnicas numéricas necesitan números aleatorios
• Programación de ordenadores: Tests de efectividad de algoritmos
• Toma de decisiones: Se rumorea que algunos ejecutivos tiran monedas al aire para tomar decisiones.
• Estética: Un toque de aleatoriedad puede resultar agradable
• Juegos: De aquí proviene el propio método para generación de números aleatorios

2.2 GENERACIÓN DE NÚMEROS PSEUDOALEATORIOS

En los experimentos de simulación es necesario generar valores para las variables aleatorias representadas estas por medio de distribuciones de probabilidad.

Para poder generar entradas estocásticas (probabilisticas) para un modelo de simulación, se debe contar con un generador de números pseudoaleatorios. Con estos y métodos de generación de variables aleatorias, se pueden simular las entradas incontrolables para un modelo de simulación. Inicialmente los números aleatorios se generaban en forma manual o mecánica utilizando técnicas como ruedas giratorias, lanzamientos de dados, barajas. También existen métodos aritméticos que permiten generan un gran conjunto de números aleatorios, pero el advenimiento de la computadora ha permitido crear generadores que permitan generar de manera sucesiva todo los números aleatorios que se requieran.

Un número pseudoaleatorio no es más que el valor de una variable aleatoria x que tiene una distribución de probabilidad uniforme definida en el intervalo (0, 1). Se sabe que la función de densidad f(x) de una variable aleatoria x con una distribución de probabilidad uniforme.

Finalmente para que para que un conjunto de números sean considerados aleatorios deben cumplir las siguientes características:

• Deben estar uniformemente distribuidos.

• Deben ser estadísticamente independientes.

• Su media debe ser estadísticamente igual a ½.

• Su varianza debe ser estadísticamente igual a 1/12.

• Deben ser reproducibles.

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 Neuman y Metropolis. 

Es el método de los cuadrados medios, se requiere de un número entero detonador (llamado semilla), con D dígitos, el cual es elevado al cuadrado y se extrae los D dígitos del centro; el primer número ri se determina simplemente anteponiendo “0.”. Para obtener el segundo ri se sigue el mismo procedimiento, solo que ahora se eleva al cuadrado los D dígitos del centro que se seleccionaron para obtener el primer ri. A continuación, se presenta con más detalles los pasos para generar números con el algoritmo de cuadrados medios

Seleccionar una semilla (Xo) con D dígitos (D>3).

Sea Xo = resultado de elevar Xo al cuadrado; sea X1 = los D dígitos del centro y sea ri = 0.D dígitos del centro.

Sea Yi = resultado de elevar Xi al cuadrado; sea Xi+1 =los D dígitos del centro y sea ri =  0.D dígitos del centro para toda i = 1,2,3…n.

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

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

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

Obtener n=4 números pseudo aleatorios con el algoritmo de los cuadrados medios.

Se elige como semilla inicial un número al azar de 4 dígitos (en nuestro caso)

Xo=5729

Lo elevamos el cuadro (5729)2= 32821441

Y0=32821441 e. Seleccionamos los 4 dígitos del centro de Y0.

X1=8214 obtenemos el nuevo número y el r0=0.8214

Luego volvemos a repetir los pasos de c a f para obtener el siguiente hasta completar los n dígitos requeridos

2.2.2 ALGORITMO DE PRODUCTOS MEDIOS

El producto medio se define como la cantidad promedio producida, por cada unidad de un determinado factor. Si este factor es el trabajo, es producto medio es el promedio producido por cada trabajador. Para obtener el producto medio debemos dividir el producto total, por la cantidad utilizada del factor.

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 ri = 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 conformarán un segundo número ri. Entonces 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; del producto se obtiene el tercer número ri. Siempre se ira eliminando el número más antiguo, y el procedimiento se repetirá hasta generar los n números pseudo aleatorios.

Pasos para hacer algoritmo de productos medios

Seleccionar una semilla (X0) con D dígitos (D>3).

Seleccionar una semilla (X1) con D dígitos (D>3).

Sea Y0 = X0 * X1; sea X2 = los D dígitos del centro, ya sea ri = 0. D dígitos del centro.

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

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

Este método tiende a degenerar a un valor constante. Tanto el método de cuadrados medios como el de producto medio tienen un periodo corto para la cantidad de números aleatorios que vamos a necesitaremos generar en cada uno de nuestros modelos.

2.2.3. ALGORITMO DE MULTIPLICADOR CONSTANTE 

Este algoritmo no congruencial es similar al algoritmo de productos medios. Los siguientes son los pasos necesarios para generar números pseudo aleatorios con el algoritmo de multiplicador constante. Pasos para generar números pseudo aleatorios con el algoritmo de multiplicador constante

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

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

1. Sea Y0= a*X0; sea X1= los D dígitos del centro, y sea ri= 0. D dígitos del centro.

1. 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.

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

El Método Congruencial Multiplicativo al igual que el congruencial mixto genera una sucesión de números pseudos aleatorios en la cual el sucesor Xn+1 del número pseudo aleatorio Xn es determinado justo a partir de Xn, de acuerdo a la siguiente relación de recurrencia:

Para ilustrar la obtención del período de un generador utilizando el Método Congruencial Multiplicativo, suponga que se tiene un generador con los siguientes parámetros:

a=5; X0=5 y m=32 

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

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:

Xi+1= (axi + c) mod (m)           I = 0,1,2,3,4…..,n

Donde X0 es la semilla, a es la constante multiplicativa, c es una constante aditiva y  m es el modulo; X0 > 0, a > 0, c > 0 y m > 0 deben ser números enteros. La operación “mod m” significa multiplicar Xi , por a, sumar c y dividir el resultado entre m para obtener el residuo i+1. Es importante señalar que la ecuación recursiva del algoritmo congruencial 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:

   ri = xi/ m-1                                                      i-1,2,3,…..,n

2.2.5. MÉTODO CONGRUENCIAL MULTIPLICATIVO 

Se puede apreciar en Tabla 2.6 que el período del generador es ocho, esto es la sucesión se repite una vez que se obtuvo el octavo número generado.El procedimiento para obtener los números pseudo aleatorios se realiza de la siguiente forma, donde la semilla es 5.

2.2.6. MÉTODO CONGRUENCIAL ADITIVO  

Calcula una sucesión de números pseudoaleatorios mediante la relación

 Xn+1= Xn +Xn-k (mod M). 

Para usar este método se necesitan k valores iniciales, siendo k entero. Las propiedades estadísticas de la secuencia tienden a mejorarse a medida que k se incrementa. Este es el único método que produce periodos mayores que M.

su ecuación es:

2.2.7 ALGORITMO CONGRUENCIAL NO LINEAL  

2.2.7.1 ALGORITMO CONGRUENCIAL  CUADRATICO 

Este algoritmo tiene la siguiente ecuación recursiva:

XI+1= (aX2i+ bXi + c )mod (m)                    i= 0, 1, 2, 3, ….

En este caso los números ri pueden ser generados por la ecuación ri= xi/(m-1), las condiciones que deben cumplir los parámetros m, a, b y c para alcanzar un periodo máximo de N=m son :

M= 2a

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 máximo N = m

2.2.7.2 ALGORITMO DE BLUM, BLUM, BLUM 

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

Xi+1= (xi2)mod(m)                        i= 0, 1, 2, 3, ….., n

La ecuación anterior fue propuesta por Blum, Blum y Shub como un nuevo método para generar número que no tienen un comportamiento predecible

Fuente:

Sanchez, Juan. Universidad Católica de Valparaíso.

http://www.material_simulacion.ucv.cl/en%20PDF/aleator11.pdf

Departamento de Física Teórica. Universidad Complutense

http://teorica.fis.ucm.es/programas/MonteCarlo.pdf

Correa, Gabriela. Universidad de Antioquia

http://docencia.udea.edu.co/ingenieria/isi-494/contenido/exposicion.html