Date post: | 03-Oct-2015 |
Category: |
Documents |
Upload: | andrea-martinez |
View: | 257 times |
Download: | 4 times |
Generadores de Nmeros
Aleatorios
Jorge Eduardo Ortiz Trivio
http://www.docentes.unal.edu.co/jeortizt/
Contenido:
Qu entendemos por secuencia de nmeros aleatorios?
Cmo se generan n. aleatorios
Generadores congruenciales lineales
Propiedades de los GCL
Otros tipos de generadores
De Tausworthe (feedback shift register)
Barajados (??) (shuffled)
Elemento Central en la Simulacin digital.
Definicin formal controvertida.
Elemento esencial en muchas reas del conocimiento
Ingeniera, Economa, Fsica, Estadstica, etc.
Definicin intuitiva: Una sucesin de nmeros aleatorios
puros, se caracteriza por que no existe ninguna regla o plan
que nos permita conocer sus valores.
Los nmeros aleatorios obtenidos a travs de algoritmos
recursivos se llaman pseudoaleatorios.
Nmeros Aleatorios
Disponer de un buen generador de nmeros aleatorios es clave en: Computacin Aleatorizada Computacin Evolutiva Algoritmos Aleatorizados Verificacin de Algoritmos Validacin de Algoritmos Criptografa etc.
Nmeros Aleatorios
La gran disponibilidad de generadores de nmeros
aleatorios en muchos entornos y compiladores puede
llevarnos a pensar que para un usuario de la simulacin
no sera necesario estudiar estas cuestiones.
Una leccin del pasado reciente nos obliga a sacar
lecciones y actuar con mucho cuidado con dichos
generadores (RANDU - IBM).
El Uso progresivo de modelos de simulacin cada vez
ms detallados exige una mayor calidad de los
generadores de nmeros aleatorios.
Nmeros Aleatorios
NMEROS ALEATORIOS
0, x < 0
F(x) x, 0 x 1
1, x
Qu entendemos por secuencia de nmeros aleatorios?
En teora, realizacin de secuencia de v.a.u U1, U2, ..., Un, ... iid, Ri U(0,1)
En la prctica criterios menos estrictos: n-distributividad: todas las n-tuplas {(Ui, Ui+1 ..., Ui+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 {(U5i,U5i+1)}, {(U5i+1,U5i+2)},
{(U5i+2,U5i+3)}, {(U5i+3,U5i+4)}, {(U5i+4,U5i+5)} uniformes sobre (0,1)x(0,1)
ALGORITMO GENERADOR DE BITS
PSEUDOALEATORIOS
Entrada:
Dos primos p,q , elegir e, tal que mcd (e, )=1, donde =(p-1)(q-1) .
Una semilla x0 [1,n-1] Algoritmo:
a) Para j=1 hasta k:
a1) xj=(xj-1)e mod n
a2) zj=el menor bit significativo de xj
Salida:
La sucesin z1, z2, , zk.
Generadores de nmeros.
Caractersticas deseables: Los nmeros generados no se deben repetir frecuentemente
(en ciclos).
Las series generadas deben ser reproducibles.
Rapidez en la obtencin de los nmeros.
Almacenamiento mnimo.
Los nmeros generados han de estar uniformemente distribuidos.
Los valores deben ser independientes unos de otros.
Mtodos De Generacin
Mtodos manuales: Generacin de nmeros con artificio manuales: bolillas, patentes de los autos, gua telefnica
Ventajas: Son aleatorios y son Simples,
Desventajas: No reproducibles y Lentos
Tablas de biblioteca: La mas importante: A milln randon digist editorial RAND, configurada con las radiaciones termoinicas de un tubo de rayos catdicos.
Ventaja: Provienen de un fenmeno aleatorio
son reproducibles.
Se las puede estudiar y analizar rigurosamente antes de ser utilizada.
Desventaja: No se obtiene en tiempo real.
Necesidades de memoria.
Mtodos De Generacin
Mtodos De Computacin Analgica: Generados con procesos fsicos aleatorios (Ej: una corriente elctrica). Ventaja: Aleatorios. Desventaja: No reproducible.
Mtodos De Computacin Digital: Con computadoras: Provisin Externa: Se graba en memoria las tablas Randa. Procesos Fsicos Aleatorios: Usar algn dato interno de la computadora
(temperatura, segundos, ciclos, cantidad de memoria asignada, etc).
Relacin de recurrencia: Generar nmeros pseudoaleatorios por medio de ecuaciones de recurrencia en las que necesariamente se tiene que dar un valor inicial o semilla para obtener los siguientes valores. Ventaja:
Son reproducibles. No afectan en demasa al procesador ni sobrecargan la memoria. Existe la posibilidad de su absoluta reproduccin
Desventaja: Son pseudoaleatorios. Hay que probar la Calidad Aleatoria del mtodo.
Uniformemente distribuido (sin recurrencia):
Es recurrente cuando uno o varios elementos se repiten con mayor frecuencia terica, => disminucin de frecuencia de los dems nmeros.
Estudiar la recurrencia de : 2, 6, 6, 8, 7, 6, 6, 6, 4, 7, 2, 6, 5, 6, 2,6,6,7, 6, 5, 4, 3, 3, 6, 6, 6, 2, 9,4,8,6,4,6, 9,6,3,7,6,9,6, 0.
Hay 40 Nmeros, por lo tanto la frecuencia terica de cada uno de los dgitos (del 0 al 9) deber ser 4.
De una tabla de frecuencias se obtiene que el digito 6->F(6)=18 veces.
Propiedades de los Nmeros aleatorios
Estadsticamente independientes (sin periodicidad):
Tiene periodicidad cuando varios elementos, repetidos o no, formando una cadena, aparecen en
la misma secuencia.
Estudiar periodicidad de:
1,0,2,2,6,8,2,3,3,0,1,0,2,2,6,8,4,1,7,0,2,2,6,8, 7,6,5,3,3,5,1,0,2,2,6,8.....
Secuencia peridica 02268. . de Frecuencia 4
1,0,2,4,6,8,2,3,3,0,1,0,2,4,6,8,4,1,7,0,2,4,6,8, 7,6,5,3,3,5,1,0,2,4,6,8.....
Secuencia peridica 02468. de Frecuencia 4
Propiedades de los Nmeros aleatorios
Reproducibles: Cuando el Mtodo comienza con la misma Semilla, DEBE dar la misma secuencia de nmeros
Pseudoaleatoreos.
Rpidos, velocidad de generacin acorde a las necesidades.
Mnimos de memoria.
Propiedades de los Nmeros Pseudoaleatorios
Conclusiones:
Hay que verificar la calidad estadsticas de las series.
Comprobarlas en tiempo de Ejecucin es una perdida de
tiempo, entonces se prueba la calidad estadstica del Mtodo.
Por la cantidad de nmeros que se necesitan y por la velocidad
de su ocurrencia, es imprescindible generarlos en la medida
que se lo necesiten.
Algunas ideas o propiedades de los generadores
I. Lagarias (1993) public un trabajo titulado Pseudo
Random Numbers en Statistical Science. Donde estudia
algunas propiedades tales como:
Expansividad : Una aplicacin es expansiva si
La idea es escoger d como una aplicacin expansiva de
manera que la inestabilidad computacional proporcione
aleatoriedad.
]1,0[1|)('| xxd
2]1,0[d
Nmeros Aleatorios
No Linealidad: La composicin de aplicaciones no lineales
puede conducir a comportamientos crecientemente no
lineales Ej: d(x) = x2; d(n)(x) = x2n
Complejidad Computacional: La aleatoriedad de
Kolmogorov, tambin denominada incomprensibilidad
computacional. Consiste en constatar si la aleatoriedad de
una sucesin de nmeros es incomprensible (problema
decidible).
Impredecibilidad
Nmeros Aleatorios
DEF 1: Kolmogorov (1987) [Complejidad Algortmica]
Una sucesin de nmeros es aleatoria sino puede producirse
eficientemente de una manera ms corta que la propia serie. DEF 2: LEcuyer (1990) [Impredicibilidad] Una sucesin de
nmeros es aleatoria si nadie que utilice recursos
computacionales razonables puede distinguir entre la serie y
una sucesin de nmeros verdaderamente aleatoria de una
forma mejor que tirando una moneda legal para decidir cul
es cul.
Obs: Esta definicin conduce a los denominados
generadores PT-perfectos usados en Criptografa.
Nmeros Aleatorios
DEF 3: Un Nmero aleatorio es una realizacin de una variable aleatoria que tiene asociada una ley de probabilidades F, en un espacio o modelo de Probabilidades (, , P).
Obs: Una particular Ley de Probabilidad base para la
generacin de nmeros pseudo-aleatorios es:
u1, u2,..., un : es la uniforme (0 ; 1) ui ~ U(0,1).
DEF 4: Una sucesin de nmeros aleatorios {u1, u2,..., un} es una sucesin de nmeros U(0;1), si tiene las mismas propiedades estadsticas relevantes que dicha sucesin de nmeros aleatorios.
Nmeros Aleatorios
DEF 5: Una sucesin de nmeros aleatorios {ui} es
aleatorio si h-plas de nmeros sucesivos no
superpuestos se distribuyen aproximadamente. como
una [0,1]h, con h=1,2,..,n, para n suficientemente
grande.
Obs: h=2 tenemos (ui,ui+1) , i=1,2,..n , se distribuye
como una ley uniforme en [0,1]2.
Existe una gran de mtodos para generar
{ui} U(0,1) : -Uniformente distribuidas
- Independientes
- E[U]= ; V[U]= 1/12
- Perodo largo
Nmeros Aleatorios
A las propiedades estadsticas anteriores se deben
agregar otras relativas a la eficiencia computacional:
Velocidad de respuesta
Consumo de memoria
Portabilidad
Parsimonia
Reproducibilidad
Mutabilidad
Perodo
Nmeros Aleatorios
Mtodos de Generacin de Nmeros Aleatorios
1.- Mtodo de los cuadrados medios
2.- Mtodos Congruenciales
3.- Mtodo de registros desfasados
[Semilla - Algoritmo - Validacin]
P1 : Obtener semilla (valores iniciales)
P2 : Aplicacin de Algoritmos recursivos
P3 : Validacin del conjunto de datos
generados (Test de Aleatoriedad)
Nmeros Aleatorios
Consiste en que cada nmero de una sucesin es producido
tomando los dgitos medios de un nmero obtenido
mediante la elevacin al cuadrado.
P1 : Obtener semilla (valores iniciales 445)
P2 : Aplicacin de Algoritmos recursivos (elevar
al cuadrado)
P3 : Validacin del conjunto de datos
generados
Mtodos 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 ............... ...............
Mtodos de los Cuadrados Medios