Números aleatorios (página 2)

Partes: 1, 2

A las propiedades estadísticas anteriores se deben
agregar otras relativas a la eficiencia computacional:

Velocidad de respuesta
Consumo de memoria
Portabilidad
Parsimonia
Reproducibilidad
Mutabilidad
Período
Números Aleatorios

Métodos de Generación de Números Aleatorios

1.- Método de los cuadrados medios
2.- Métodos Congruenciales
3.- Método de registros desfasados

[Semilla – Algoritmo – Validación]
P1 : Obtener semilla (valores iniciales)
P2 : Aplicación de Algoritmos recursivos
P3 : Validación del conjunto de datos generados (Test de Aleatoriedad)

Números Aleatorios

Consiste en que cada número de una sucesión es producido tomando los dígitos medios de un número obtenido mediante la elevación al cuadrado.
P1 : Obtener semilla (valores iniciales 445)
P2 : Aplicación de Algoritmos recursivos (elevar al cuadrado)
P3 : Validación del conjunto de datos generados
Métodos de los cuadrados Medios

Ejemplo: Consideremos la semilla 445

X X2 N° Aleatorio
445 1| 9802 | 5 0,9802
9802 96| 0792 | 04 0,0792
792 6 | 2726 | 4 0,2726
2726 …………… ……………

Métodos de los Cuadrados Medios

Xn+1 = (a Xn + b) mod m ;

Los parámetros del algoritmo se llaman
– a multiplicador
– b sesgo
– m módulo
– Xo semilla (valor inicial)

Generadores Congruenciales

Obs: 1.- Cuando b=0 el generador se denomina Generador congruencial multiplicativo.
2.- Cuando b?0 el generador se denomina Generador congruencial mixto.
3.- A pesar de la simplicidad una adecuada elección de los parámetros de “a, b y m”, permite obtener de manera eficiente una larga e impredecible sucesión de números como para considerarse “aleatoria”.
Generadores Congruenciales

Generadores Congruenciales

Algunas observaciones de las salidas de los generadores congruenciales:
i) Un generador congruencial tiene ciclos
iI) La longitud del ciclo depende de la selección de los parámetros (ver caso 1) y 3) )
iii) Dentro de selecciones de parámetros que conducen a la misma longitud, algunas salidas parecen más aleatorias que otras.
iv) La representación de pares (Xi, Xi+1) sugiere que estos se disponen en un número finito de hiperplanos.
Generadores Congruenciales

Los resultados teóricos que veremos a continuación facilitan la elección de los parámetros de “a y b” su demostración puede verse en el texto clásico
D. Knuth (1981):
“The Art of Computer Programming”. Ed. A. Wesley Vol N°2
Generadores Congruenciales

Proposición 2.1
Un generador congruencial tiene su período máximo si y sólo si:
i) m.c.d (b, m) = 1 (primos relativos)
ii) a = 1 mod p ; para cada factor primo p de m.
iii) a = 1 mod 4 ; si 4 divide a m.
Puesto que b esta asociado en la práctica con el efecto de traslación, inicialmente asumiremos ( b=0), es decir partiremos estudiando los generador congruencial multiplicativos.
Generadores Congruenciales

Dem: Donald Knuth Vol 2 (1981)
Obs: 1) Lo anterior sugiere elegir “m” lo más grande posible, para asegurarnos un período largo (posibles elecciones de m son; m=231 -1, m=216 +1)
2) Sea p el período de la secuencia de números aleatorios, si p=m el generador se llama de período completo.
3) Si m es un número primo entonces el máximo período se obtiene ssi a =1
Generadores Congruenciales

Proposición 2.2 Sea un generador multiplicativo (b=0) [Xn+1 = a Xn mod m] tiene período p=(m-1), sólo si “p” es primo. El periodo divide a (m-1) y es (m-1) si y sólo si “a” es una raíz primitiva de m-1, es decir a(m-1)/p ? 1 mod m, para todos los factores primos p de (m-1).
Proposición 2.3
Si a es un raíz primitiva de m, ak mod m, lo es siempre que k y m-1 sean primos relativos.
Equivalentemente
Si a es una raíz primitiva de m, ak mod m lo es siempre que ; mcd(k,m-1)=1
Generadores Congruenciales

Dem: B. Ripley (1987) “Stochastic Simulation”Ed. John Wiley. pp 47
Obs: 1) En general los generadores congruenciales son de la forma
Xn+1 = g (Xn, Xn-1,…. ,Xn-k ,…) mod m

g (x) = a Xn
g (x) = a Xn + b
g (x) = a Xn2 + b Xn + c

Usando g (x) = (a1 Xn-1 + a2 Xn-2 + … + ar Xn-r), se obtiene
un generador de Fibonacci retardado. La teoría de estos generadores se puede ver en Marsaglia (1985)]
Generadores Congruenciales

2) Una buena elección de “m”, permite obtener un generador eficiente (ciclo máximo). Pero aún se debe estudiar con más detalle la elección de a y b, pues se tienen muchos grados de libertad.
3) Un buen generador congruencial debe ser:
i) De máximo período
ii) Su salida debe parecer aleatoria

iii) Poder implementar de forma eficiente en aritmética
de 32 bits.
Generadores Congruenciales

Un algoritmo de muy fácil implementación del tipo congruencial es m = 231-1
a = 75 (raíz primitiva de m)
Xn = 75 Xn-1 mod (231-1)
un =

Dicho generador se encuentra en las bibliotecas IMSL y NAG
Generadores Congruenciales

La rutina RANDU, que IBM proporcionaba para sus equipos consideraba un modelo congruencial multiplicativo con m = 231 ; a = 65539 ; b = 0
Xn = 65539 Xn-1 mod (231)
un =

¡ Este generador proporciona tripletas consecutivas de números que caen en 15 planos ! Lo que sugiere cierta previsiblidad en su salida (Mal Generador)
Generadores Congruenciales

Barsaglia (1968) demostró que sucesiones consecutivas no superpuestas de n números aleatorios obtenidos de generadores multiplicativos caen en, a lo sumo [n! m] 1/n hiperplanos paralelos.
Algunas cotas de casos representativos
n=3 n=5 n=7 n=9 n=10
m = 216 73 23 16 14 13
m = 232 2953 220 80 48 41
Es decir, en un computador con palabras de 32 bits, menos de 41 hiperplanos contendrán las 10-úplas
Generadores Congruenciales

En teoría puede conseguirse que un buen generador con m = 232 produzca 357.913.941 puntos independientes en un cubo de dimensión 3, siendo el mínimo número de hiperplanos que contiene estos puntos 108, en contraste con los 2953.
Para la famosa rutina RANDU de IBM,
Xn = 65539 Xn mod (231)
las tripletas consecutivas de números caen en 15 planos.
Generadores Congruenciales

Se basa en Generadores lineales recursivos múltiples

El estudio de este generador se asocia al Polinomio característico.
sobre un
álgebra finita Fm, con m elementos. [Niederreiter 1992]
Generadores de Registros Desfasados

[Niederreiter 1992]

Cuando el polinomio es primitivo el período es (mk-1). Debido a la complejidad del análisis para m grande, habitualmente se elige un m pequeño, generalmente 2 obteniendo generadores de bits de la forma

donde ak = 1 ^ ai ? {0, 1}
Generadores de Registros Desfasados

La adición módulo 2 es equivalente al XOR (ó exclusivo)
0 XOR 0 = 0 0 XOR 1 = 1
1 XOR 1 = 0 1 XOR 0 = 1
Esto nos permite implementar registros de desplazamiento
Un generador propuesto Tausworthe (1985)

Generadores de Registros Desfasados

En este caso los primeros q bits deben ser especificados, esto es análogo a la semilla de los generadores congruenciales.
Este tipo de generador depende del largo de la palabra
Ejemplo: h = 3 ; q = 5 ; b1 = b2 = b3 = b4 = b5 = 1
b6 = (b3 + b1) mod 2 = 2 mod 2 = 0
b7 = (b4 + b2) mod 2 = 2 mod 2 = 0
b8 = (b5 + b3) mod 2 = 2 mod 2 = 0
b9 = (b6 + b4) mod 2 = 1 mod 2 = 1
b10 = (b7 + b5) mod 2 = 1 mod 2 = 1
…
b42 = (b39 + b37) mod 2 = 2 mod 2 = 0
Generadores de Registros Desfasados

Transformar la sucesión {bi} en un número aleatorio U(0,1)

Consideremos {bi}

b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12
1 1 1 1 1 0 0 0 1 1 0 1
……… b41 b42
……… 1 0

Conversión del Generador Binario

Consideremos l = 4
y1 = b123 + b222 + b321 + b420 = 8 + 4 + 2 + 1 = 15
u1 =
y2 = b523 + b622 + b721 + b820 = 8 + 0 + 0 + 0 = 8
u2 =
y3 = b923 + b1022 + b1121 + b1220 = 8 + 4 + 0 + 1 = 13
u3 = …. y así sucesivamente
Conversión del Generador Binario

Dada la estructura reticular de los generadores lineales, algunos autores sugirieron utilizar generadores no lineales. (Ver Niederreiter (1992))
Usar un generador con función de transición lineal, produciendo una transformación no lineal del estado en su salida.
Usar un generador con función de transición no lineal.
Generadores no Lineales

Una forma de incrementar el periodo e intentar evitar regularidades que muestren los generadores lineales es combinar (mezclar) diferentes generadores para obtener generadores híbridos de mejor calidad que los generadores originales.
Muchas de las combinaciones propuestas son heurísticas y algunas con resultados bastantes pobres.
Por ejemplo sean e dos sucesiones aleatorias, una sucesión combinada sería :
Zi = Xi Yi
donde “ ” es alguna operación binaria
Combinación de Generadores

Generadores Paralelos de números aleatorios.
Sincronización; reproductibilidad; gasto transición ]
Generadores de Fibonacci retardados
[ Sincronización; reproductibilidad; gasto transición ]
Generadores Comerciales: IMSL Generador congruencial multiplicativo m = 231 – 1 a = 16807; 397204094; 950706376
http://www.stat.cmu.edu/
Otros Generadores

Finalmente la fase de validación se basa en ciertas propiedades estadísticas que deben cumplirse a la salida de los generadores de n° aleatorios .
Los Test empíricos que veremos a continuación son genéricos y pueden usarse en la evaluación de generadores de n° aleatorios, en generadores de variables aleatorias y en la modelación de entradas de modelos de simulación.
La mayoría de los Test se encuentran disponibles en paquetes estadísticos comerciales. SAS, Statistica, etc.
Validación de Generadores Congruenciales

1) Test
Este es un test de Bondad de Ajuste. Es poco potente, por lo que permite justificar el rechazo de una hipótesis, pero proporciona escaso apoyo en la aceptación.
Dada una muestra X1, X2, …, Xn de una Fx(x) desconocida. Se desea contrastar.
Ho : Fx(x) = Fo(x) v/s H1 : Fx(x) ? Fo(x)

Validación de Nos Aleatorios

Efectuando una partición del soporte de X en k subconjuntos I1, I2, …, Ik :

fi : frecuencia absoluta del subconjunto i-ésimo (Ii)
ei: número de observaciones esperadas en Ii bajo Ho
~
asint
Validación de Nos Aleatorios

Obs: 1) Este Test considera aleatoridad de Fo = U(0,1)
2) Este Test también permite contrastar la uniformidad S-dimensional de
X1 = (u1, u2, …, us);
X2 = (us+1, us+2, …, u2s);
…
Xn = (u(n-1)s+1, …, uns)

en Fo = [0,1]s [Distribución uniforme en el hipercubo]
Validación de Nos Aleatorios

2) Test de Kolmogorov – Smirnov (Test K-S)
Sea Fo una función de distribución continua y sea Fn la función de distribución empírica de la muestra.
Bajo Ho: Fx(x) = Fo(x) se espera que Fn se aproxime a Fo
Dn = Sup | Fn(x) – Fo(x) |

La distribución exacta de Dn está tabulada para valores n ? 40 y distintos niveles de significación ?.
Para muestras grandes se utiliza la distribución asintótica de Dn dada por

x ? R
Validación de Nos Aleatorios

Obs: En el caso particular de aleatoridad se considera
X(1) < X(2) < …. < X(n)

estadísticos de orden Fo(X(i)) = X(i) ^ Fn (X(i)) = i/n

Dn =
Test de Kolmogorov – Smirnov

3) Test de Rachas
Dada la sucesión de “n” observaciones construimos la sucesión de símbolos binarios definida por

Definimos racha creciente (decreciente) de longitud “L” a un grupo seguido de “L” números 1(+) ó números 0(-). Contando el número de rachas. Bajo aleatoridad de la muestra se espera que su distribución asintótica sea normal:

N
Validación de Nos Aleatorios

Ejemplo: Considere la siguiente secuencia de 20 números aleatrorios
0.43 0.28 0.33 0.27 0.12
0.31 0.42 0.01 0.32 0.45
0.98 0.79 0.99 0.55 0.67
0.74 0.16 0.20 0.12 0.58
– + – – + + – + + + – + – + + – + – +
L=14 E[L]= 13, V[L]=3.23 Z = (14 -13) /
Z = 0.55 comparado con el valor crítico N ( 13 ;3.23)
El supesto de independencia no puede ser rechazado

Test de Rachas por encima y debajo de la mediana.
Se cuentan el número de observaciones que se sitúan a un mismo lado de la mediana. La distribución asintótica del número de rachas bajo aleatoridad es normal:
N
Test de Rachas

4) Test Serial
Este Test se usa para contrastar el grado de aleatoriedad entre números aleatorios sucesivos de una secuencia. [Extensión del test Chi-Cuadrado]

Sea
X1 = (u1, …, uk) X2 = (uk+1, …, u2k) … Xn = (u(n-1)k+1,…, unk)

Consideremos la n (k-úplas). Se desea contrastar que X1, X2, …, Xn son v.a.i.i.d. uniformemente distribuidas en el hipercubo k-dimensional unitario.
Test Serial

Dividiendo el hipercubo rk en hipercubos elementales de volumen 1/rk y sea Vj1, j2, …, jk el número de k-úplas que caen dentro del elemento

usando la estadística
Test Serial

Caso Especial (k=2)
X1 = (u1, u2) X2 = (u3, u4) … Xn/2 = (u(n-1), un)

Particularmente el eje X e Y en r subintervalos de igual longitud, generando r2-cubos del mismo tamaño. El número de pares esperado por cubo es

Test Serial

Entonces la estadística
Sea nij : el número de pares en el cuadrado (i, j)
i = 1,r j =1,r
Test Serial

Otros Test son:
Test de Permutaciones
Test de Poker
Test de Dependencia
Test de longitud de rachas
etc.
Validación de Nos Aleatorios