Post on 22-Jan-2020
transcript
Generación de variables aleatorias continuasMétodo de rechazo
Georgina Flesia
FaMAF
18 de abril, 2013
Método de Aceptación y Rechazo
RepasoI Se desea simular una v. a. X discreta, con probabilidad de masa
pj = P(X = j), j = 0,1,2, . . . .I Hipótesis: Se conoce un método eficiente para generar una v.a.
Y , con probabilidad de masa qj = P(Y = j), j = 0,1,2, . . . , queverifica
I Si pj 6= 0 entonces qj 6= 0.I Existe una constante c (c > 1) tal que
pj
qj≤ c para todo j tal que pj > 0
Método de Aceptación y Rechazo
Algoritmo: Método de aceptación y rechazorepeat
Simular Y , con probabilidad de masa qY ;Generar U ∼ U(0,1)
until U < pY/cqY ;X ← Y
TeoremaEl algoritmo de aceptación y rechazo genera una variable aleatoriadiscreta tal que
P(Xj ) = pj , j = 0,1, . . . .
Además, el número de iteraciones requeridas para obtener X es unav.a. geométrica con media c.
El método de rechazo
Veamos la version para variables continuas
I Sea X una v. a. con densidad f : F (x) = P(X ≤ x) =∫ x−∞ f (t) dt .
I Supongamos que se tiene un método para generar Y , condensidad g, y que
f (y)
g(y)≤ c, para todo y ∈ R tal que f (y) 6= 0.
El método de rechazo para generar X a partir de Y tiene el siguientealgoritmo:
Método de rechazo
Algoritmo: Método de aceptación y rechazorepeat
Generar Y , con densidad g;Generar U ∼ U(0,1)
until U < f (Y )/(cg(Y ));X ← Y
Teorema1. La v. a. generada por el método de rechazo tiene densidad f .2. El número de iteraciones del algoritmo es una variable aleatoria
geométrica con media c.
Cálculo de la cota c
h(x) =f (x)
g(x)≤ c
¿Es h acotada superiormente? ¿Existe un máximo de h?
I Determinar puntos críticos de h.I Un punto crítico x0 es un máximo local de h si en un entorno
(a,b) de x0 ocurre:I h′(x) > 0 para x < x0 y h′(x) < 0 para x > x0, oI h′′(x0) < 0.
I Evaluar h en los extremos del intervalo.
Ejemplo
Utilizar el método de rechazo para generar una v. a. con función dedensidad
f (x) = 20x(1− x)3, 0 < x < 1.
f (x) =Γ(α + β)
Γ(α)Γ(β)xα−1(1− x)β−1I(0,1)(x) Variable β
I X es una v. a. Beta (2,4).I Está acotada en (0,1).I Se puede aplicar el método de rechazo con g(x) = 1, 0 < x < 1.I Hallar c tal que
f (x)
g(x)=
f (x)
1≤ c
Ejemplo
h(x) =f (x)
1= 20x(1− x)3, 0 < x < 1
h′(x) = 20(1− x)2 · (1− 4x)
I Puntos críticos: x = 1 y x = 1/4.I h(0) = h(1) = 0, luego 0 y 1, los extremos del intervalo, no son
máximos.I h(1/4) = 135/64 > 0 por lo cual x = 1/4 es un máximo.I h(1/4) = f (1/4) = 135/64 es el valor máximo de h
c =13564
= 2.109375
Ejemplo
I Puntos críticos: x = 1 yx = 1/4.
I f (1) = 0, luego no es unmáximo.
I x = 1/4 es un máximo.I h(1/4) = f (1/4) = 135/64 es
el valor máximo: c.
Ejemplo
f (x)
c g(x)=
f (x)
135/64=
1280135
x(1− x)3 =25627
x(1− x)3
Algoritmo: Método de aceptación y rechazorepeat
Generar V ∼ U(0,1);Generar U ∼ U(0,1)
until U < 25627 V (1− V )3;
X ← V
I El promedio del número de ciclos es c =13564≈ 2.11.
Ejemplo
Generar una v. a. con densidad gamma ( 32 ,1):
f (x) = Kx1/2e−x , x > 0,
con K = 1/Γ( 32 ) = 2/
√π.
X ∼ gamma(α, β) =βα
Γ(α)e−βxxα−1.
E [X ] = α/β.
I X toma valores reales, no negativos.I En el ejemplo, la media es 3/2.I Es razonable rechazar con una exponencial de igual media.
Pero podemos despues verificar si no podemos hacer unalgoritmo mejor.
Ejemplo: generación de gamma (32 ,1)
I Y ∼ E( 23 )
I g(x) = 23 e−2/3 x , x > 0.
I h(x) = f (x)/g(x) =3K2 x1/2e−x/3
I c = 3( 3
2πe
)1/2
Ejemplo
h(x) =f (x)
g(x)= CTE x1/2e−x/3, 0 < x
h′(x) = CTE [12
x−1/2e−x/3 + x1/2−13
e−x/3]
0 =12
x−1/2e−x/3 + x1/2−13
e−x/3
|x | =32
I Puntos críticos: 32 cuando x>0.
I h(0) < h( 32 ); h(2) < h( 3
2 ), luego 0 extremo del intervalo, no esmáximo y h( 3
2 es el máximo.
I h( 32 = 3
( 32πe
)1/2por lo cual
c = 3(
32πe
)1/2
Generación de una v. a. exponencialSabemos que
I Si X ∼ E(λ), entonces c · X también es exponencial.
I c · X ∼ E(λ
c).
I Calculamos la inversa de la función de distribución de X ∼ E(1):
FX (x) = 1− e−x
u = 1− e−x
1− u = e−x
x = − loge(1− u)
X ∼ E(1)
Generar U;X ← −log(U)
X ∼ E(λ)
Generar U;
X ← −1λ
log(U)
Ejemplo: generación de gamma (32 ,1)
f (x)
cg(x)=
(2e3
)1/2
x1/2e−x/3
Algoritmo: Método de rechazorepeat
Generar V ∼ U(0,1);Y ← − 3
2 log(V );Generar U ∼ U(0,1)
until U <( 2e
3
)1/2Y 1/2e−Y/3;
X ← Y
c = 3(
32πe
)1/2
≈ 1.257
Ejemplo
I ¿Es cierto que es ”razonable” rechazar con una exponencial deigual media que la gamma?
Tomamos g(x) = λe−λx , exponencial con razón λ, media 1/λ.Obtenemos:
f (x)
g(x)=
Kx1/2e−(1−λ)x
λ, 0 < λ < 1
Máximo en → x =1
2(1− λ), 0 < λ < 1.
Valor máximo → c =Kλ
(2(1− λ))−1/2e−1/2.
λ =23
minimiza el valor de c.
Generación de una v. a. normal
EjemploGenerar una v. a. normal estándar, es decir, Z con densidad
f (x) =1√2π
e−x2/2.
I |Z | tiene densidad f|Z |(x) = 2√2π
e−x2/2, en 0 < x <∞.
I Si sabemos generar |Z |, generamos Z por composición.
Generación de una v. a. normal
Para generar |Z |:I Elegimos g(x) = e−x ,
0 < x <∞.I Resulta c =
√2e/π
I c ≈ 1.32.
Generación de una v. a. normal
f (x)
cg(x)= exp
{− (x − 1)2
2
}.
Generación de |Z |repeat
Generar V ∼ U(0,1);Y ← − log(V );Generar U ∼ U(0,1)
until U < exp{− (Y−1)2
2 };|Z | ← Y
I U < exp{− (Y−1)2
2 }
I − log(U) > (Y−1)2
2I Y2 = − log(U) ∼ E(1).
Generación de una v. a. normal
Generación de |Z |repeat
Generar Y1 ∼ E(1);Generar Y2 ∼ E(1)
until Y2 > (Y1 − 1)2/2};|Z | ← Y1
I Si Y2 > (Y1 − 1)2/2}, entonces X = Y2 − (Y1 − 1)2/2 esexponencial con media 1, por la propiedad de falta de memoria.
I Luego podemos generar la normal y también una exponencial.
Generación de una v. a. normal
Generación de Z normal y X exponencialrepeat
Generar Y1 ∼ E(1);Generar Y2 ∼ E(1)
until Y2 − (Y1 − 1)2/2 > 0;X ← Y2 − (Y1 − 1)2/2;Generar U ∼ U(0,1);if U < 0.5 then
Z = Y1else
Z = −Y1end