clase3. generación y verificación de numeros aleatorios
DESCRIPTION
Generación y verificación de numeros aleatoriosTRANSCRIPT
Para generar una simulación se requiere
numeros aleatorios en el intervalo de [0,1]
Generación de números pseudo
aleatorios
Generación de numeros pseudo
aleatorios
ci
ni
si
si
ei
ei
ei
Ci = variables exogenas
• Algunas de las variables de entrada son de tipo aleatorio por lo que se
tendrán que generar valores que simulen dichas entradas.
• Para generar variables aleatorias que sigan determinadas funciones de
probabilidad necesitamos partir de series de números que cumplan la
aleatoriedad.
Propiedades deseadas de buenos
generadores
El método más común es generar el siguiente
número a partir de los últimos números generados
Una de estas funciones es:
Si comenzamos con xo = 5, los primeros 32 números
generados son: 10, 3, 0, 1, 6, 15, 12, 13, 2, 11, 8, 9,
14, 7, 4, 5, 10, 3, 0, 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7,
4, 5
Propiedades deseadas de buenos
generadores
Los números generados: 10, 3, 0, 1, 6, 15, 12,
13, 2, 11, 8, 9, 14, 7, 4, 5, 10, 3, 0, 1, 6, 15,
12, 13, 2, 11, 8, 9, 14, 7, 4, 5
Algoritmos de cuadrados mediosAlgoritmo no congruencial, propuesto por Von Neumann y
Metropolis.
1. Seleccionar una semilla (Xo) con D dígitos (D>3)
2. Sea Yo= resultado de elevar Xo al cuadrado, sea X1= los D
dígitos del centro, y sea ri=0.D dígitos del centro.
3. Sea Yi=resultado de elevar Xi al cuadrado; sea Xi+1=los D
dígitos del centro, y sea ri=0.D dígitos del centro para toda
i=1,2,3,…n.
4. Repetir el paso 3 hasta obtener los n números ri, deseados.
Ejemplo: Generar los primeros 5 números ri, a partir de una semilla
Xo=5735, de donde se puede observar que D=4 dígitos
Algoritmos de productos medios1. Seleccionar una semilla (Xo) con D dígitos (D>3)
2. Seleccionar una semilla (X1) con D dígitos (D>3)
3. Sea Yo= Xo * X1,sea X2= los D dígitos del centro, y sea ri=0.D
dígitos del centro.
4. Sea Yi= Xi * Xi+1; sea Xi+2=los D dígitos del centro, y sea ri+1 =
0.D dígitos del centro para toda i=1,2,3,…n.
5. Repetir el paso 4 hasta obtener los n números ri, deseados.
Ejemplo: Generar los primeros 5 números ri, a partir de una semilla
Xo=5015 y X1=5734; observe que ambas semillas tienen D=4
dígitos.
Algoritmo de multiplicador constante1. Seleccionar una semilla (Xo) con D dígitos (D>3)
2. Seleccionar una constante (a) con D dígitos (D>3)
3. Sea Yo= a * X0, sea X1= los D dígitos del centro, y sea ri=0.D dígitos del centro.
4. Sea Yi= a *Xi; sea Xi+1 = los D dígitos del centro, y sea ri+1 = 0.D dígitos del centro para toda i=1,2,3,…n.
5. Repetir el paso 4 hasta obtener los n números ri, deseados.
Ejemplo: Generar los primeros 5 números ri, a partir de una semilla Xo = 9803 y con la constante a = 6915.
Algoritmo linealAlgoritmo congruencial propuesto por D.H. Lehmer en 1951.
Xi+1=(aXi + c) mod (m) i=0,1,2,3,….,n.
ri = Xi+1 / (m-1) i=0,1,2,3,…,n.
Ejemplo: Generar 5 números entre 0 y 1 con los siguientes
parámetros: Xo=37, a=19, c=33 y m=100.
Donde:
Xo= semilla
a= constante multiplicativa
c= constante aditiva
m = modulo
Algoritmo linealPara lograr un máximo periodo de vida “n”. Banks,Carson, Nelson
y Nicol sugiere:
m=2^g
a = 1+4k
Donde:
k y g debe ser entero
C relativamente primo a m.
Bajo estas condiciones el periodo de vida máximo: N = m = 2^g
Ejemplo: Generar números entre 0 y 1 con los parámetros Xo=6,
k=3, g=3 y c=7, hasta encontrar el periodo máximo (N)
a= 1+4(3)=13 y m = 2^3=8
Algoritmo lineala= 1+4(3)=13 y m=2^3=8
Xo=6
X1=(13*6 +7)mod 8 = 5 r1=5/7=0.714
X2=(13*5 +7)mod 8 = 0 r2=0/7=0.000
X3=(13*0 +7)mod 8 = 7 r3=7/7=1.000
X4=(13*7 +7)mod 8 = 2 r4=2/7=0.285
X5=(13*2 +7)mod 8 = 1 r5=1/7=0.142
X6=(13*1 +7)mod 8 = 4 r6=4/7=0.571
X7=(13*4 +7)mod 8 = 3 r7=3/7=0.428
X8=(13*3 +7)mod 8 = 6 r8=6/7=0.857
Xi+1=(a *Xi + c)mod(m) i=0,1,2,3,….,n.
ri=Xi/m-1 i=0,1,2,3,…,n.
Algoritmo congruencial multiplicativo Surge del algoritmo congruencial lineal cuando c=0. entonces la
ecuación recursiva es:
Xi+1=(aXi) mod (m) i=0,1,2,3,….,n.
ri=Xi/(m-1)
De acuerdo con Banks,Carson, Nelson y Nicol sugieren lo
siguiente:
m = 2^g
a = 3+8k ó a=5+8k
A partir de estas condiciones se logra un periodo de vida
máximo N = m/4 = 2^(g-2)
K=0,1,2,3,….
Xo debe ser impar
g debe ser entero
Algoritmo congruencial multiplicativo
Ejemplo: Generar los suficientes números entre 0 y 1
con los siguientes parámetros: Xo=17, k=2 y g=5,
hasta encontrar el periodo o ciclo de vida.
Xi+1=(aXi)mod(m) i=0,1,2,3,….,n.
ri=Xi/(m-1)
N=m/4=2^(g-2)
m=2^g
a = 3+8k ó a=5+8k
Algoritmo congruencial aditivo Este algoritmo requiere una secuencia previa de “n”
números enteros X1, X2,…,Xn para generar una
nueva secuencia de números enteros que empieza
en Xn+1, Xn+2,…..
Su ecuación recursiva es:
Xi=(Xi-1 + Xi-n) mod (m) i=n+1, n+2, n+3,…., N
Los números ri = Xi / (m-1)
Algoritmo congruencial aditivoEjemplo: Generar 7 números pseudo aleatorios entre
cero y uno a partir de la siguiente secuencia de
números enteros: 65, 89, 98, 03, 69. m=100
Xi=(Xi-1 + Xi-n) mod (m) i=n+1, n+2, n+3,…., N
Algoritmo congruencial cuadrático
Xi+1=(a*(Xi)^2 + b*Xi +c) mod (m) i=0,1,2,…,N
ri=Xi/(m-1)
De acuerdo con L’Ecuyer las condiciones que
debe cumplir los parámetros m,a,b y c para
alcanzar un periodo máximo de N=m son:
m=2^g
Donde:
a= debe ser numero par
c= debe ser numero impar
g debe ser entero
(b-1)mod 4 = 1
Algoritmo congruencial cuadratico
Ejemplo: Generar, a partir del algoritmo
congruencial cuadrático, suficientes números
enteros hasta alcanzar el periodo de vida,
considerando los parámetros Xo=13, m=8, a=26,
b=27 y c=27Xi+1=(a*(Xi)^2 + b*Xi +c) mod(m)
i=0,1,2,…,N
ri=Xi/(m-1)