Numeros aleatorios

MÉTODOS DE SIMULACIÓN
Capítulo 1. Generación de números aleatorios

Capítulo 1. Generación de números aleatorios

ÍNDICE
1. 2. Introducción Contrastes empíricos - Uniformidad (Contraste χ2 y Kolmogorov-Smirnov) - Aleatoriedad (Rachas, Test de Póker) - Repetición de contrastes Generadores congruenciales Otros generadores - Registro de desplazamiento - Fibonacci retardados - No lineales -Combinación de generadores - Generadores paralelos - Generadores comerciales Conclusiones

3. 4.

5.

Capítulo 1. Generación de números aleatorios

1. Introducción
Disponibilidad de un buen generador de números aleatorios. Es un elemento esencial en muchas otras áreas de la Informática (algoritmos aleatorizados, verificación de algoritmos, complejidad de algoritmos, criptografía,...), de laEstadística (métodos de muestreo y remuestreo, contrastes Montecarlo, Inferencia Bayesiana...), .... Además, un elemento importante en aplicaciones como juegos para ordenador, protectores de pantallas,... La disponibilidad de generadores de números aleatorios en muchos entornos y compiladores haría pensar que para un mero usuario de la Simulación no sería necesario estudiar estas cuestiones. Sinembargo, una lección que se deriva del estudio de algunos generadores comerciales es que debemos actuar con sumo cuidado con ellos (área de investigación bastante activa).

Capítulo 1. Generación de números aleatorios

Problema: escoger una fuente de números aleatorios y obtener de esta fuente suficientes números para nuestro experimento de simulación. Orígenes históricos. Tablas de númerosaleatorios: Tippet (1927): Universidad de Cambridge, 10.000 números aleatorios de 4 dígitos basados en censos. Royo y Ferrer (1954): 250.000 resultados de la lotería nacional (INE). Rand Corporation (1954): 1 millón de números aleatorios mediante el uso de mecanismos físicos (ruleta electrónica, medición de ruido electrónico...). Inconveniente del uso de mecanismos físicos falta de reproducibilidad.Procedimientos algorítmicos de generación de números La idea (von Neumann) es producir números que parezcan aleatorios, empleando las operaciones aritméticas del ordenador: partiendo de una semilla inicial (u0, u1,..., u-p+1), generar una sucesión mediante ui = d(ui-1,..., ui-p), para cierta función d.

Capítulo 1. Generación de números aleatorios

¿qué se considera como secuencia denúmeros aleatorios? Definición clásica de Kolmogorov (Kolmogorov y Uspenskii, 1987) (asociada a la idea de complejidad algorítmica). Una sucesión de números es aleatoria si no puede producirse eficientemente mediante un programa más corto que la propia serie. Criterio de Turing (IA). Una suc. de nºs es aleatoria si nadie que utilice recursos computacionales razonables en t. razonable puede distinguirentre la serie y una sucesión verdaderamente aleatoria de una forma mejor que tirando una moneda fiel para decidir cuál es cuál. (Generadores PT-perfectos usados en criptografía). Definición basada en la Estadística. Una sucesión de números aleatorios (ui) es una sucesión de números en (0,1) con las mismas propiedades estadísticas relevantes de una sucesión de números aleatorios (Uniformidad en(0,1) o bondad de ajuste y aleatoriedad o independencia estadística). Otras propiedades relativas a la eficiencia computacional: 1) Rapidez; 2) Poco consumo de memoria; 3) Portabilidad; 4) Sencillez en la implementación; 5) Reproducibilidad y mutabilidad; 6) Periodo suficientemente largo.

Capítulo 1. Generación de números aleatorios

2. Contrastes empíricos Bondad de ajuste o uniformidadContraste χ2 El contraste χ2 de Pearson es el más antiguo y válido para distribuciones continuas y discretas. Sin embargo, es poco potente, por lo que permite justificar el rechazo de una hipótesis, pero proporciona escaso soporte para su aceptación. Supongamos que tenemos una muestra x1,...,xn (n ≥ 25) de una población con función de distribución Fn(x) desconocida y deseamos contrastar la hipótesis...