Download Generación de Números Aleatorios

Generación de Números
Seudo-Aleatorios
En la práctica ninguna función
produce datos aleatorios
verdaderos.
Las funciones producen números
pseudo-aleatorios.
1
Generación de Números
Seudo-Aleatorios
Un elemento importante en simulación es tener
rutinas que generen variables aleatorias con
distribuciones específicas: uniforme, normal, etc.
Para ello la base es generar una secuencia de
números aleatorios distribuidos uniformemente entre
0 y 1.
2
Y para ello la clave es generar números enteros
aleatorios y uniformemente distribuidos en un cierto
intervalo de una manera eficiente.
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.
3
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
4
X22 = (7089)2 = 50,253,921 ===> X3 = 2539
Operación mod

k mod m es el residuo de hacer la división de
k entre m
Sea x un entero grande
45 mod 12 =
(5+55x) mod 5 =
(5+55x) mod 11 =
5
Método de la Congruencia Lineal
6
7
El número aleatorio se encuentra de la siguiente manera:
R = x /m
8
Ejercicio 1
a = 12
9
c= 0
Usar Excel para calcular los números aleatorios
que se producen para m = 15, a = 12 y c = 0
con las semillas x0 = 0, hasta 14.
m = 15
x0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
x1
x2
x3
x4
x5
x6
x7
x8
x9
x 10
x 11
x 12
0
12
9
6
3
0
12
9
6
3
0
12
9
6
3
0
9
3
12
6
0
9
3
12
6
0
9
3
12
6
0
3
6
9
12
0
3
6
9
12
0
3
6
9
12
0
6
12
3
9
0
6
12
3
9
0
6
12
3
9
0
12
9
6
3
0
12
9
6
3
0
12
9
6
3
0
9
3
12
6
0
9
3
12
6
0
9
3
12
6
0
3
6
9
12
0
3
6
9
12
0
3
6
9
12
0
6
12
3
9
0
6
12
3
9
0
6
12
3
9
0
12
9
6
3
0
12
9
6
3
0
12
9
6
3
0
9
3
12
6
0
9
3
12
6
0
9
3
12
6
0
3
6
9
12
0
3
6
9
12
0
3
6
9
12
0
6
12
3
9
0
6
12
3
9
0
6
12
3
9
Ejercicio
Usar Excel para calcular los números aleatorios
que se producen para m = 15, a = 12 y c = 0
con las semillas x0 = 0, hasta 14.
Para x0 = 1: ¿Cuál es el período, la longitud es del
ciclo y la longitud de la cola ?.
R: 5, 4, 1.
10
Ejercicio
11
Usar Excel para calcular los números aleatorios
que se producen para m = 15, a = 12 y c = 0
con las semillas x0 = 0, hasta 14.
GCL Multiplicativos
Periodo completo = Cuando tiene el máximo periodo
posible, m – 1.
Los hay con m potencia de 2 (m = 2k ) que son rápidos pues el
residuo en divisiones con potencia de 2 puede hacerse rápidamente.
Aunque tienen la desventaja que no son de periodo completo
pueden ser suficientes para muchas aplicaciones.
12
Cuando m no es potencia de 2 el generador es menos rápido; se
acostumbra elegir un número m que sea primo y la relación entre m y
a debe ser especial para que el generador tenga un periodo
completo o al menos grande.
13
14
Ejercicio 2
Suponiendo que se utilice el generador de números
seudo-aleatorios.
y que la semilla se escoge eligiendo al azar un entero
entre 1 y 26 − 1 inclusive, determine el promedio de
la longitud del periodo y su desviación estándar.
15
Varianza y Desviación Estándar
para una muestra de datos.

x

 x  X   x  n
2
n
Varianza:
S 
2
i 1
Desviación Estándar:
16
2
i
n 1

s  s2
i
2
i
n 1
Ejercicio
1. Determina el rango, la varianza y la desviación estándar para los
siguientes datos:
2
4
3
5
2
2
0
1
R = Rango 5; Varianza 2.5536 y Desviación Estándar 1.5980
2. Determina el rango, la varianza y la desviación estándar para los
siguientes datos:
-2
-4
-3
-5
-2
-2
0
-1
R = Rango 5; Varianza 2.5536 y Desviación Estándar 1.5980
17
3. Determina el rango, la varianza y la desviación estándar para los
siguientes datos:
6
12
9
15
6
6
0
3
R = Rango 15; Varianza 22.9821 y Desviación Estándar 4.7940
Ejercicio
Frecuentemente se utilizan generadores de números seudoaleatorios en forma encadenada; por ejemplo, el número que
sale de
xn+1 = (81 ・xn + 121) mod 255
es utilizado por
yn+1 = (625 ・ xn+1 + 48) mod 63
18
para producir el número yn+1 que es el que se reporta.
Usando la semilla x0 = 23 y los datos anteriores, determine los
primeros 2 números aleatorios generados (y1 y y2).
Otro ejercicio
Frecuentemente se utilizan generadores de números seudoaleatorios en forma encadenada; por ejemplo, el número que
sale de
xn+1 = (45 ・xn + 71) mod 127
es utilizado por
yn+1 = (125 ・ xn+1 + 11) mod 63
19
para producir el número yn+1 que es el que se reporta.
Usando la semilla x0 = 49 y los datos anteriores, determine los
primeros 2 números aleatorios generados (y1 y y2).
Probando generadores de
números aleatorios
Es importante asegurarse de que el generador usado
produzca una secuencia suficientemente aleatoria.
Para esto se somete el generador a pruebas
estadísticas. Si no pasa una prueba, podemos asumir
que el generador es malo. Pasar una prueba es una
condición necesaria pero no suficiente. Un generador
puede pasar una prueba y luego no pasarla si se usa
otra semilla u otro segmento del ciclo.
20
¿Cómo sabemos que nuestro
generador es bueno?
PRUEBAS GRÁFICAS
• Gráfica de Serie de Tiempo.
• Tablas de frecuencias e histogramas
PRUEBA ESTADÍSTICA
• Prueba Ji-cuadrada
• Usar el ejemplo: xn+1 = (75 ・xn) mod 231 – 1
Con semilla = 1, los primeros 200 números generados.
21
Gráfica de Serie de Tiempo
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
1
11
21
31
41
51
61
71
81
91
101 111 121 131 141 151 161 171 181 191 201
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
22
20
40
60
80
100
120
140
160
xn+1 = (75 ・xn) mod 231 – 1
Con semilla = 1, los primeros 200 números generados
180
200
Es
importante
observar que
NO exista
ningún
patrón o
tendencia.
¿Cómo sabemos que nuestro
generador es bueno?
¿Cuál de estas series de números
parecen venir de un buen generador?
Generador Uniforme?
Generador Uniforme
1.25
random
1
0.75
0.5
0.25
0
-0.25 0
-0.5
1
0.8
0.6
0.4
0.2
0
0
23
50
100
Tabla de frecuencias e histograma
Intervalo Frecuencia
24
21
19
20
16
25
20
20
17
20
22
200
Histograma
30
25
Frecuencias
[0, 0.1)
[0.1, 0.2)
[0.2, 0.3)
[0.3, 0.4)
[0.4, 0.5)
[0.5, 0.6)
[0.6, 0.7)
[0.7, 0.8)
[0.8, 0.9)
[0.9, 1.0)
20
15
10
5
0
[0, 0.1) [0.1,
0.2)
[0.2,
0.3)
[0.3,
0.4)
[0.4,
0.5)
[0.5,
0.6)
Intervalo
[0.6,
0.7)
[0.7,
0.8)
[0.8,
0.9)
[0.9,
1.0)
Números aleatorios entre 0 y 1
f(x)
1, 0  x  1
f(x) =
1
0, en otro caso
1
x
F(x)
0, x < 0
F(x) =
x, 0  x  1
1
1, x<1
1
25
x
Números aleatorios entre 0 y 1
* 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).
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.
26
Prueba estadística Ji-cuadrada
Esta es la prueba más comúnmente usada. En general, puede ser usada
para cualquier distribución.
A partir de un histograma, se comparan las frecuencias observadas
con las frecuencias obtenidas de la distribución específica (frecuencias
esperadas).
Intervalo
I1
I2
…
Ik
27
Frecuencia
Observada
O1
O2
…
Ok
Total
Frecuencia
Esperada
E1
E2
…
Ek
Total
Prueba estadística Ji-cuadrada
 Hipótesis nula.
Ho: no hay diferencia entre frecuencias
observadas y esperadas.
 Hipótesis alternativa. Ha o H1 : existe una diferencia entre
frecuencias observadas y esperadas.
Estadístico de prueba:
28
Si el ajuste es exacto, c02 es cero, pero por aleatoriedad no lo
será. Se puede demostrar que tiene distribución ji-cuadrado con
k-1 grados de libertad.
Distribución Ji-cuadrada
29
Ejercicio:
Determine el 95º percentil de la distribución ji-cuadrada con 6 grados de libertad.
Prueba estadística Ji-cuadrada
Los grados de libertad son iguales a: número de filas - 1
Región de Rechazo:
c  c ,k 1
2
0
30
2
En esta prueba se debe
cuidar que las frecuencias
esperados sean mayores
o iguales a 5.
Prueba estadística Ji-cuadrada
Ejercicio 3
Generador:
xn+1 = (75 ・xn) mod 231 – 1
Con semilla = 1, los primeros 200 números generados.
Realizar la prueba estadística ji-cuadrada para probar si los
valores vienen de una distribución uniforme.
Usar nivel de significancia =  = 0.05
 Ho: Los valores provienen de una distribución uniforme.
 Ha: Los valores NO provienen de una distribución uniforme.
31
Prueba estadística Ji-cuadrada
Ejercicio 3
Frecuencia
Intervalo
Observada
[0, 0.1)
[0.1, 0.2)
[0.2, 0.3)
[0.3, 0.4)
[0.4, 0.5)
[0.5, 0.6)
[0.6, 0.7)
[0.7, 0.8)
[0.8, 0.9)
[0.9, 1.0)
Total
10
c 
2
0
32
i 1
Frecuencia
Esperada
21
19
20
16
25
20
20
17
20
22
200
Oi  Ei 
20
20
20
20
20
20
20
20
20
20
200
(observado - esperado) 2
esperado
0.05
0.05
0
0.8
1.25
0
0
0.45
0
0.2
2.8
2
Ei
 2.8
Estadístico de prueba
Prueba estadística Ji-cuadrada
Ejercicio 3
Región de Rechazo:
c  c ,k 1
2
0
2
c2 ,k 1  c 02.05,9
 16.919
33
2.8 no es mayor que 16.919,
por lo que el estadístico de
prueba NO cae en la región
de rechazo.
Conclusión: Ho NO se rechaza.
Los valores generados sí parecen
venir de una distribución uniforme
Ejercicio 4
Generador:
xn+1 = (57 ・xn) mod 215 – 1
Con semilla = 1, considere los primeros 100 números generados
entre 0 y 1.
Realizar la prueba estadística ji-cuadrada para probar si los valores
vienen de una distribución uniforme.
Usar 10 intervalos.
Usar nivel de significancia =  = 0.05.
34
Ejercicio 5
Usando el método del cuadrado medio y
semilla = 5896, se generaron los
primeros 80 números aleatorios.
Realizar la prueba estadística jicuadrada para probar si los valores
provienen de una distribución uniforme.
Usar 8 intervalos y un nivel de
significancia =  = 0.05.
35
Intervalo
Frecuencia
[0, 0.125)
[0.125, 0.25)
[0.25, 0.375)
[0.375, 0.5)
[0.5, 0.625)
[0.625, 0.75)
[0.75, 0.875)
[0.875, 1.0)
16
12
11
11
8
6
7
9
80
Ejercicio 6
Generador:
xn+1 = (57 ・xn) mod 215 – 1
Con semilla = 14, considere los primeros 100
números generados entre 0 y 1.
Realizar la prueba estadística ji-cuadrada
para probar si los valores vienen de una
distribución uniforme.
Usar 8 intervalos.
Usar nivel de significancia =  = 0.05.
36
Intervalo
Frecuencia
[0, 0.125)
[0.125, 0.25)
[0.25, 0.375)
[0.375, 0.5)
[0.5, 0.625)
[0.625, 0.75)
[0.75, 0.875)
[0.875, 1.0)
22
7
18
13
21
4
9
6
100
Generación de variables
aleatorias discretas
Suponga que un determinado fenómeno aleatorio tiene la
siguiente distribución de probabilidad:
Variable
18 cm.
37
Probabilidad Acumulada
0.3
0.3
19 cm.
0.4
0.7
20 cm.
0.3
1
0  R  0.3
entonces x = 18 grs.
0.3 < R  0.7
entonces x = 19 grs.
0.7 < R  1
entonces x = 20 grs.
Para esto, se necesitan números aleatorios R entre 0 y 1.
Ejercicio 7
Usar el generador:
xn+1 = (57 ・xn) mod 215 – 1
Con semilla = 1.
a) Generar 100 valores de la distribución:
Variable
18 cm.
38
Probabilidad
0.3
19 cm.
0.4
20 cm.
0.3
b) Utilizar la prueba ji-cuadrada para decidir si los valores
generados realmente parecen tener la distribución de
probabilidad anterior ( = 0.05).
c) Usar 20 semillas y observar en cuántos casos la prueba se
rechaza.
Números aleatorios con distribución
normal
En Excel.
=NORMINV(RAND(),500,50)
aleatorio entre 0 y 1 media desv. std.
(puedes usar tu
propio generador)
39
Ejercicio 8
Usar el generador:
xn+1 = (59 ・xn) mod 217 – 1
Con semilla = matrícula menor del equipo.
a) Generar 500 valores de la distribución uniforme continua entre 0 y 1 con el
generador.
b) Usar esos valores para generar 500 números aleatorios de la distribución
normal con media 100 y desviación estándar 16 (distribución del puntaje de
IQ).
c) Utilizar la prueba ji-cuadrada para decidir si los valores generados realmente
parecen tener la distribución normal ( = 0.01).
En la tabla de frecuencias, calcular a mano 3 frecuencias esperadas (mostrar
procedimiento usando editor de ecuaciones). Escribir conclusión (sí o no se
trata de un buen generador de números normales).
d) Construir el histograma de frecuencias observadas y el histograma de
frecuencias esperadas.
40
e) Usar 20 semillas y observar en cuántos casos la prueba se rechaza. Indicar
qué semillas se usaron y cuál fue el valor del estadístico en cada caso.