Kupdf.com istracion De La Cadena De Suministro Una Perspectiva Logistica 9a Ed 2013 Coyle Langley Novack Gibson(1) odt

Generación de números aleatorios Programa de doctorado en Biometría y Estadística

Simulación numérica de modelos estocásticos Departament d’Estadística Divisió de Ciències Experimentals i Matemàtiques

2

Contenido:  ¿Qué entendemos por secuencia de

números aleatorios?  Cómo se generan n. aleatorios  Generadores congruenciales lineales  Propiedades de los GCL  Otros tipos de generadores – De Tausworthe (“ shift ”) – “Barajados” (??) (“shuffled”) Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

¿Qué entendemos por secuencia de números aleatorios?

3

 En teoría, realización de secuencia de

v.a. R1, R2, ..., Rn, ... iid, Ri  U(0,1)  En la práctica criterios menos estrictos: – n-distributividad: todas las n-tuplas {(Ri, Ri+1 ..., Ri+n-1)} uniformes sobre (0,1)n – (k,n)-distributividad: cada k-ésima subsecuencia de longitud n uniforme (0,1)n • p.e. (5,2) seria {(R5i,R5i+1)}, {(R5i+1,R5i+2)}, {(R5i+2,R5i+3)}, {(R5i+3,R5i+4)}, {(R5i+4,R5i+5)} uniformes sobre (0,1)x(0,1) Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

4

Cómo se generan n. aleatorios  Dispositivos físicos “aleatorios” (ruletas,

contadores de rayos cósmicos, ...) ± auténticamente aleatorios no repetible, difícil conexión con programas

 Algoritmo recursivo (determinista) repetible (total control sobre la secuencia generada), informáticamente “natural” “pseudoaleatorio”, limitaciones intrínsecas a aleatoriedad: ciclos, autocorrelación, ... Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

5

Generadores congruenciales lineales (GCL)

multiplicador

 Producen secuencia de enteros no

negativos {Xi}, 0  Xi < m-1, a partir de semilla inicial X0, mediante X i + 1 = (aX i + c ) mod m (i = 0, 1, K )

a, m > 0

c³ 0

módulo incremento

Y secuencia de “números aleatorios” mediante Ri = Xi/m, Ri  [0,1) Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

6

Propiedades de los GCL  A pesar de sus limitaciones son los más

usados (y mejor conocidos): – Período: menor entero k tal que Xk=X0 (¡y la secuencia se repite!). Siempre k  m. – Período completo sii k = m. Condición necesaria y suficiente (Hull y Dobell): • c primo respecto de m • (a-1) múltiplo de q, para todo factor primo q de m • (a-1) múltiplo de 4, si m lo es Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

7

GCL mixtos (c > 0)  Ordenadores binarios: si m = 2b, mod

es simple desplazamiento de bits. Si 32 bits: m = 231 o m = 232 (período alcanzable  4,29·109), (16 bits período alcanzable 215=32767 o 216=65534)  En este caso período completo si c impar y (a-1) múltiplo de 4. Pega: período de los últimos d bits también del orden de 2d Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

8

GCL multiplicativos (c = 0)  1ª condición de Hull y Dobell imposible

de cumplir nunca período completo.  Recomendable m primo. Si a es un elemento primitivo módulo (EPM) m  período igual a m-1 (Knuth)  Escoger m primo lo más grande posible (cerca de 2b, b núm. bits) y a EPM m  m primo y m = 2h-1 (primo de Mersene)  mod eficiente (ideal h=b) Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

9

Los tres tipos de GCL en el software actual  Información escasa, en general: Tipo A: mixtos de período completo, m = 2b, a-1 múltiplo de 4, c impar (NAG?) Tipo B: multiplicativos de período máximo dado m (es decir, período m-1), m primo, a elemento primitivo modulo m (Simpscript II) Tipo C: multiplicativos, m=2b, a-5 múltiplo de 8, período = m/4. Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

10

Propiedades estadísticas calculables teóricamente T ipo A: m - 1 E (R ) = 2m

m2 - 1 var (R ) = 12 m 2

T ipo B: 1 E (R ) = 2

m 2 - 2m var (R ) = 12 m 2

Autocorrelación: solamente algunas cotas, complicadas y no muy útiles. Estructuras de mayor orden (n-distributividad) propiedades en general muy malas en este tipo de generadores, especialmente para pocos Dep. bits. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

11

Otros tipos de generadores  Generador lineal congruencial general

X i = (a1X i - 1 + K + a p X i -

p

)mod m

p > 1, a p ¹ 0 No hay repetición hasta que

(X 0 , K , X p - 1 ) = (X k , K , X k + p - 1 ) Potencialmente, período máximo mp-1. p=2, a1=a2=1: de Fibonacci (muy malos) Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

12

Generadores de Tausworthe. I  Caso de generador lineal congruencial

general con m primo. Período máximo si xp - a1xp-1 ... - ap es un polinomio primitivo módulo m  Tausworthe: si m=2: secuencia de bits, ai = 0 ó 1. Suelen emplearse trinomiales de forma xp + xq + 1, p > q  recurrencia: X i = X i - p xor X i - (p - q ) Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

13

Generadores de Tausworthe. II  Posteriormente estos bits agrupados en

enteros de longitud L (L  p), según bits por entero deseados. Q bits de espacio para siguiente entero (Q  L).  Más independientes de la máquina  Propiedades estadísticas de primer y segundo orden y n-distributividad mucho mejores que en congruenciales. Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques

14

Otros métodos  “Shuffled”: propuestos diversos

algoritmos para “barajar” de alguna manera la salida de otro generador.  Otra posibilidad es combinar generadores, p.e. mediante xor – Se puede demostrar que si Xi e Yi son aleatorias, Zi = Xi xor Yi también lo es

 Poco conocidos teóricamente, principal

ventaja parece mejor n-distributividad Dep. d’Estadística. Divisió de Ciències Experimentals i Matemàtiques