Download número random.

NÚMEROS ALEATORIOS
DEPARTAMENTO DE
INFORMATICA
UNSL-2007
NUMEROS ALEATORIOS

Los números random son un elemento básico en la
simulación de la mayoría de los
sistemas
discretos.

Cada número random Ri es una muestra
independiente de una distribución uniforme y
continua en el intervalo (0,1).
NÚMEROS ALEATORIOS
f(x)
f(x)
1,
0x 1
1
0,
en otro caso
1
F(x)
0,
x<0
x,
0x 1
1,
x<1
F(x)
1
1
NÚMEROS ALEATORIOS
* La probabilidad de observar un valor en un particular
intervalo es independiente del valor previo observado.
* Todo punto en el rango tiene igual probabilidad de ser
elegido.
* Si el intervalo (0,1) es dividido en n sub-intervalos de
igual longitud, el número esperado de observaciones en
cada intervalo es N/n. (N número de observaciones
totales).
GENERADOR DE NÚMEROS
ALEATORIOS
El objetivo de cualquier esquema de
generación (generador), es producir una
secuencia de números entre 0 y 1 que simule
las propiedades ideales de distribución
uniforme y de independencia.
NÚMEROS PSEUD0-ALEATORIOS
•Los números aleatorios son calculados a partir de
una semilla (seed) y una fórmula.
•El problema es que si el método es conocido,
entonces la secuencia de números random puede ser
replicada.
•En la práctica ninguna función produce datos
aleatorios verdaderos -- las funciones producen
números pseudo-aleatorios.
TÉCNICAS PARA GENERAR
NÚMEROS ALEATORIOS
La mayoría de los métodos (generadores) comienzan
con un número inicial (semilla), a este número se le
aplica un determinado procedimiento y así se encuentra
el primer número random.
Usando este número como entrada, el procedimiento es
repetido para lograr un próximo número random.
Y así siguiendo.
TÉCNICAS PARA GENERAR
NÚMEROS ALEATORIOS
Método Del Cuadrado Medio: comienza con un número inicial
(semilla). Este número es elevado al cuadrado. Se escogen los
dígitos del medio de este nuevo número (según los dígitos que se
deseen) y se colocan después del punto decimal. Este número
conforma el primer número random.
Ejemplo:
X0 = 5497
X02 = (5497)2 = 30,217,009 ===> X1 = 2170
R1 = 0.2170
X12 = (2170)2 = 04,708,900 ===> X2 = 7089
R2 = 0.7089
X22 = (7089)2 = 50,253,921 ===> X3 = 2539
TÉCNICAS PARA GENERAR
NÚMEROS ALEATORIOS
Método De Congruencia Lineal: produce una secuencia de
enteros X1, X2,... entre 0 y m-1 de acuerdo a la siguiente relación
recursiva:
Xi+1= (a * Xi + c) mod m,
i=0,1,2,...
X0 es llamado semilla.
a es llamado el multiplicador constante.
c es el incremento.
m es el módulo.
El número aleatorio se encuentra de la siguiente manera:
R = X /m
TÉCNICAS PARA GENERAR
NÚMEROS ALEATORIOS
Ejemplo: Utilice el método de Congruencia Lineal para generar
números aleatorios con las siguiente constantes:
X0 = 27 , a = 17, c = 43, m = 100
La secuencia de Xi y subsecuentes Ri serían:
X0 = 27
X1 = (17 * 27 + 43) mod 100 = 502 mod 100 = 2
R1 = 2/100 = 0.02
X2 = (17 * 2 + 43) mod 100 = 77 mod 100 = 77
R2 = 77/100 = 0.77
La selección de los parámetros del generador afecta drásticamente
las propiedades ideales y la longitud del ciclo.
FUNCIONES DE NÚMEROS (PSEUDO)
ALEATORIOS EN LA BIBLIOTECA
ESTÁNDAR.
El conjunto más simple de funciones es:
int rand(void);
void srand(unsigned int semilla);
Un ejemplo sencillo del uso del tiempo de la fecha es
inicializando la semilla a través de una llamada:
srand( (unsigned int) time( NULL ) );
TEST PARA EL CHEQUEO DE
UNIFORMIDAD
Generador Uniforme
1.25
1.25
1
1
0.75
0.75
random
random
Generador Uniforme
0.5
0.25
0
0.5
0.25
0
-0.25 0
-0.251 27 53 79 05 31 57 83 09 35 61 87
1 1 1 1 2 2 2 2
-0.5
-0.5
Generador Uniforme?
1
0.8
0.6
0.4
0.2
0
0
50
100
TEST PARA EL CHEQUEO DE
UNIFORMIDAD
Test de Kolmogorov-Smirnov: compara
la
distribución de un conjunto de números generados
con una distribución uniforme.
Este test compara:
la función de Probabilidad Acumulada continua F(x)
de una Distribución Uniforme, con
la función de Probabilidad Acumulada empírica
SN(x), de una muestra de N observaciones.
TEST DE KOLMOGOROV-SMIRNOV
Por definición, la Función de Probabilidad Acumulada
(teórica) uniforme entre 0 y 1 tiene:
* F(x) = x, 0<=x<=1
Mientras que una Función de Probabilidad Acumulada
Empírica se encuentra:
* SN(x) = (cantidad de n.r. generados <=x ) / N
Este test se basa en la mayor desviación absoluta entre F(x) y
SN(x) sobre todo el rango de variable random.
Esto es:
D = max|F(x) - SN(x)|
La distribución de D está tabulada como una función de N.
Ejercitación de Distribución Empírica (SN(x))
Si no se conoce la probabilidad de un fenómeno se debe
trabajar con las distribuciones empíricas ( basadas en
frecuencias).
Ejemplo: Que distribución tiene la siguiente secuencia de
números?:
3-4-5-3-4-5-3-6-4-3
valor cantidad
frel.
frelAcum
3
4
4/10=0.4
4/10=0.4
4
3
3/10=0.3
7/10=0.7
5
2
2/10=0.2
9/10=0.9
6
1
1/10=0.1
10/10=1
El test procede de la siguiente manera:
1- Ordena los datos de menor a mayor:
R(1)<=R(2)<=... <= R(N)
(R(i) denota la observación más pequeña.)
2- Computa:
D+ = max { i/N - R(i)},
1<=i<=N
D- = max { R(i)- (i-1)/N},
1<=i<=N
3- Computa D = max (D+,D-).
Ejemplo (continuación)
0.6
0.5
0.4
0.3
0.2
0.1
0
0.1 0.2 0.3 0.4 0.5 0.6
0.03
0.32
0.58
El test procede de la siguiente manera (continuación):
4- Determina el valor crítico, D para el nivel de
significancia alfa y tamaño de muestra N, (estos valores
están tabulados).
5- Si la muestra estadística diferencia ha D es mas
grande que el valor crítico, D, la hipótesis nula es
rechazada.
Si D <= D concluye que ninguna diferencia
significativa ha sido detectada entre la
verdadera
distribución de {R1,R2 ..., RN} y la distribución
uniforme.
Ejemplo Para Ejecutar Test De Uniformidad
(Kolmogorov - Smirnov)
Suponer que se generaron cinco números random y que
se desea ejecutar el test de K.S. para un nivel de
significancia  = 0.05
Orden cronológico: R1
R2
R3
R3
R5
0.03
0.58
0.87
0.32
0.95
Orden numérico creciente:
R(1)
R(2)
R(3)
R(3)
R(5)
0.03
0.32
0.58
0.87
0.95
Ejemplo (continuación)
Evaluación:
D.Teórica
F(x) = R(i)
0.03
0.32
0.58
0.87
0.95
D.Empírica
SN(x)= i/N
0.2
0.4
0.6
0.8
1
i/N – R(i)
(D+ :dif. sup.)
0.17
0.08
0.02
0
R(i) - (i-1)/N
(D- :dif. inf.)
0.03
0.12
0.18
0.27
Continuar este ejemplo.....
0.05
0.15
GENERACIÓN DE VARIABLES
ALEATORIAS EMPÍRICAS
TÉCNICA DE LA TRANSFORMADA INVERSA
DEPARTAMENTO DE
INFORMATICA
UNSL-2007
GENERACIÓN DE VARIABLES ALEATORIAS
EMPÍRICAS DISCRETAS
Suponga que un determinado fenómeno aleatorio
tiene la siguiente distribución de probabilidad:
Variable
Probabilidad
Acumulada
20 grs.
0.3
0.3
19 grs.
0.4
0.7
18 grs.
0.3
1
TECNICA DE LA TRANSFORMADA
INVERSA (Generalización de Montecarlo)
0.33
prob.acumulada
0.91
1
0.8
0.6
0.4
0.2
0
20
19
gramos
18
TECNICA DE LA TRANSFORMADA
INVERSA (Generalización de Montecarlo)
prob.acumulada
1
0.8
0.6
0.4
0.2
0
20
19
gramos
18
TECNICA DE LA TRANSFORMADA
INVERSA (Generalización de Montecarlo)
Variable
Probabilidad Acumulada
20 grs.
0.3
0.3
19 grs.
0.4
0.7
18 grs.
0.3
1
 R  0.3 entonces
x = 20 grs.
0.3 < R  0.7 entonces
x = 19 grs.
0.7 < R  1
x = 18 grs.
0
entonces
Transformada Inversa
Distribuciones Empíricas Continuas

Suponga que se han coleccionado 100
tiempos de reparación de un elemento
intev.(hs)
0.0-0.5
0.5-1.0
1.0-1.5
1.5-2.0
frecuencia frec.relativa frec.acumulda
31
0.31
0.31
10
0.10
0.41
25
0.25
0.66
34
0.34
1
Transformada Inversa
Distribuciones Contínuas
Como no se conoce la D. Acum. Teórica , trabajo con la D. Empìrica
distribución empírica
Fˆ ( x)
probabilidad
acumulada
1
1
0.8
0.66
0.6
0.4
0.41
0.31
0.2
0
0
0.5
1
1.5
tiempos de reparación
2
F(x)
Transformada Inversa
Gráficamente:
distribución empírica
Generamos
Ri= 0.83
vamos hasta
la curva y
encontramos
Xi
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
1
0.66
0.41
0.31
0
0.5
X1  F
1
Ri 
1
1.5
2
Xi
Transformada Inversa
Algebraicamente:
distribución empírica
Dado Ri= 0.83
1
(entre 0.66 y 1), 0.9
0.8
Xi es computado 0.7
0.6
por una
interpolación 0.5
0.4
lineal entre
0.3
0.2
1.5 y 2
0.1
0
1
0.66
0.41
0.31
0
0.5
1
Ri  0.66
X i  1.5 
 2  1.5
1  0.66
1.5
2
Transformada Inversa
Algebraicamente:
Dado Ri= 0.83
(entre 0.66 y 1),
Xi es computado
por una
interpolación
lineal entre
1.5 y 2
distribución empírica
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
1
0.83
0.66
0.41
0.31
0
0.5
1
0.83  0.66
1.75  1.5 
 2  1.5
1  0.66
1.5
2
1.75