congruencial

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.

3.
4.

5.

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
- Fibonacciretardados
- No lineales
- Combinación de generadores
- Generadores paralelos
- Generadores comerciales
Conclusiones

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 la Estadí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
necesarioestudiar estas cuestiones.
Sin embargo, 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ígeneshistóricos.
Tablas de números aleatorios:
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 demecanismos 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 de nú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 recursoscomputacionales razonables en t. razonable puede distinguir entre 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 relevantesde 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 aleatorios2. Contrastes empíricos
Bondad de ajuste o uniformidad
Contraste χ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...