lunes, 14 de marzo de 2011

MÉTODOS DE GENERACIÓN DE NÚMEROS ALEATORIOS


El objetivo de cualquier esquema de generación (generador),  es producir una secuencia de números entre 0 y 1 que simule las propiedades ideales de distribución uniforme y de independencia.


Un problema básico que nos encontramos habitualmente es el de obtener secuencias de números uniformemente distribuidos en un intervalo .

La diferentes posibilidades para resolver dicho problema son:

i) Buscar en tablas de números aleatorios publicadas (libros, internet ...);

ii) Observar un proceso físico tal como la desintegración radiactiva, el ruido eléctrico ...;

iii) Los lenguajes de programación y las hojas electrónicas incluyen una función para generarlos

iv) Mediante algorismos de generación de números aleatorios

Las principales ventajas de los generadores de números 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.

Los números generados deben cumplir ciertas características para que sean válidos. Dichas características son:

1. Uniformemente distribuidos.
2. Estadísticamente independientes.
3. Su media debe ser estadísticamente igual a 1/2.
4. Su varianza debe ser estadísticamente igual a 1/12.
5. Su periodo o ciclo de vida debe ser largo.
6. Deben ser generados a través de un método rápido.
7. Generados a través de un método que no requiera mucha capacidad de almacenamiento de la computadora.


Normalmente se utilizan números enteros, ya que su aritmética es exacta y rápida. Se generan enteros entre 0 y , y da valores reales en el intervarlo




En general los algoritmos utilizan relaciones de recurrencia del tipo
en el caso de recurrencia simple, o bien
para el caso de una recurrencia de orden .

Se necesitará dar un valor inicial para comenzar el algoritmo (
valores para recurrencias de orden ).
Estos generadores son los más utilizados y los más conocidos. Se basan en la relación de recurrencia
donde es el multiplicador y el módulo.

- Hay
valores posibles de , entre 0 i .

- La secuencia es periodica: cuando vuelve a aparecer un número por segunda vez, la secuencia se vuelve a repetir. El periodo depende de los valores de
, y , así como del valor inicial; nótese que el máximo posible es .

Recordemos que lo que nos interesa para trabajar con un buen generador de números aleatorios es que la distribución de los números obtenidos tiene que ser uniforme, no deben de haber correlaciones entre los terminos de la secuencia, el periodo debe ser lo más largo posible, y el algorismo debe ser de ejecución rápida.
Las limitaciones más importantes de los generadores son su periocidad (normalmente el periodo no suele ser más grande de y la posible presencia de correlaciones entre términos consecutivos de la secuencia. Una manera sencilla de suprimir éstas limitaciones es desordenar un poco la secuencia mediante el siguiente procedimiento:
Se parte de un generador que da enteros aleatorios entre 0 y
, y en primer lugar se genera con el GCL un vector que contiene una lista de enteros aleatorios , así como un entero aleatorio . Se determina el índice.







El elemento de la lista se da como un nuevo nombre aleatorio, y se reasigna a la variable el valor . El valor de se renueva con el GCL, y se vuelve a repetir los pasos desde la determinación del índice .
En estos generadores cada nuevo número entero aleatorio , se obtiene manipulando los bits del número anterior, . En lenguaje C, esto se puede hacer facilmente utilizando operadores sobre bits, .
Las grandes ventajas de estos generadores es que son generadores muy rápidos que tienen un periodo muy largo. La fomentación teorica en la que se basan es diferente a la de los GCL. Los generadores de Fibonacci se basan en una recurrencia del tipo
donde son enteros dados y denota alguna de las operaciones . Este tipo de generador precisa iniciar (con otro generador) y mantener una lista de los últimos números generados.

Otros tipos de generadores los podemos encontrar en:

- W.H. Press, S.A. Teukolski, W.T. Vetterling i B.P. Flannery, Numerical Recipes in C, Cambridge University Press.
-D.E. Knuth, The Art of computing programming, 2: Seminumerical Algorithms, Addison-Wesley.
Antes de aceptar un nuevo generador hace falta verificar que satisface una série de pruebas, lo que llamaremos pruebas de aleatoriedad.



METODOS PARA GENERAR NUMEROS ALEATORIOS NO UNIFORMES
En los modelos estocásticos existirán una o más variable aleatorias interactuando. Estas variables siguen distribuciones de probabilidad teóricas o empíricas, diferentes a la distribución uniforme (0-1). Para generar números que sigan el comportamiento de éstas variables, se pueden utilizar algunos métodos como los siguientes:
1. Método de la transformada inversa
2. Método de rechazo
3. Método de composición, y
4. Procedimientos especiales
 

MÉTODO DE LA TRANSFORMADA INVERSA.
El método de la transformada inversa utiliza la distribución acumulada F(x) de la distribución que se va a simular. Puesto que F(x) esta definida en el intervalo (0-1), se puede generar un número aleatorio uniforme R y tratar de determinar el valor de la variable aleatoria para cual su distribución acumulada es igual a R, es decir, el valor simulado de la variable aleatoria que sigue un distribución de probabilidad f(x), se determina al resolver la siguiente ecuación.
F(x) = R ó x = F^-1 (R)
La dificultad principal de este método descansa en el hecho de que en algunas ocasiones es difícil encontrar la transformada inversa. Sin embargo si esta función inversa ya ha sido establecida, generando números aleatorios uniformes se podrán obtener valores de la variable aleatorio que sigan la distribución de probabilidad deseada.


Pruebas de aleatoriedad
Éstas consisten basicamente en realizar dos tipos de pruebas, empíricas y teoricas. Si los generadores superan estas pruebas, podremos asegurar que estamos ante un generador de números aleatorios bastante competente

Pruebas empíricas (sobre la muestra de la secuencia)

- Test de uniformidad: hace falta que los valores esten uniformemente distribuidos en
. Se puede realizar un test . Alternativamente, podemos estimar los momentos de orden y comprobar que se aproximan a sus correspondientes valores teoricos, .

- Test serial: se generan parejas de valores
, y se comprueba si se distribuyen uniformemente en el cuadrado .

- Test de correlaciones: se determina la correlación entre números separados
lugares en la secuencia, . Su valor tendría que acercarse a 1/4.

Pruebas teoricas (sobre toda la secuencia): La sencillez de los generadores de congruencia lineal permiten demostrar propiedades importantes:

- Para determinar valores de
i se obtienen secuencias de periodo máximo . Por ejemplo, si es una potencia de 2, bastará con que sea impar y sea igual a un múltiple de 4 mas 1.

- Test espectral: si se forman vectores con
valores consecutivos,
estos forman hiperplanos paralelos en el espacio k-dimensional. La separación entre los planos tiene que ser la mínima posible.
El problema a tratar será el de obtener una secuencia con densidad de probabilidad dada , definida en el intervalo a partir de una secuencia de números con distribución uniforme .

HISTORIA Y DEFINICIÓN DE LOS NÚMEROS ALEATORIOS

Un número aleatorio es aquel obtenido al azar, es decir, que todo número tenga la misma probabilidad de ser elegido y que la elección de uno no dependa de la elección del otro. El ejemplo clásico más utilizado para generarlos es el lanzamiento repetitivo de una moneda o dado ideal no trucado.

Los primeros juegos de azar tuvieron su origen en el 3500 AC con la utilización de huesos en Egipto y otros lugares, dichos huesos pueden ser considerados como los antecesores de los dados.
En el si XVII, un noble francés, Antoine Gombauld (1623-16222), puso en tela de juicio el fundamento matemático del éxito y del fracaso de las mesas de juegos. Por tal motivo dirigió su duda al matemático francés Blaise Palscal (1623-16662): “¿Cuáles son las probabilidades de que salgan dos seieses por lo menos una vez en veinticuatro lanzamiento de un par de dados?”, Blaise resolvió el problema. Más tarde y con la ayuda del famoso matemático Pierre de Fermat (1601-1665) y los dos anteriores dieron vida a la primera revista académica dedicada a la probabilidad.
Más tarde Jacob Bernoulli, Abraham Moivre, el reverendo Thomas Bayes y Joseph Lagrange inventaron formulas y tecnicas de porbabilidad. Para el siglo XIX Pierre Simon, Marquez de Laplace unifico esas primera ideas y formulo la primera teoría de probabilidad. Hoy día la teoria de probabilidad es ampliamente utilizada en areas de ingeniería, ciencias y administración.
La historia formal de los números aleatorios surge en la dÉcada de los cuarenta, con el método de simulación de montecarlo, von neuman, metropolis, ulam y lehmer pueden ser nombradoe como los pioneros en este campo.
Ante la venida de los computadores se hizo posible el generar números speudo- aleatorios para reemplazar los métodos físico utilizados hasta el momento.
FUENTE:http://ciruelo.uninorte.edu.co/pdf/ingenieria_desarrollo/8/numeros_aleatorios.pdf