Generación de variables aleatorias discretasMétodo de aceptación y rechazo
Método de composiciónMétodo de la urnaMétodo de tablas
Georgina Flesia
FaMAF
11 de abril, 2013
Método de Aceptación y Rechazo
I Se desea simular una v. a. X discreta, con probabilidad de masapj = 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
Algorithm 1: 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 aleatoria Xa valores enteros no negativos tal que
P(X = j) = pj , j = 0,1, . . . .
Además, el número de iteraciones requeridas para obtener X es unav.a. geométrica con media c.
Demostración
Sea X el valor generado por el algoritmo 1. Quiero ver que
P(X = j) = pj
. Observemos queI (X = j) si y sólo si (Y = j) y el algoritmo lo acepta en alguna
iteración:
P(X = j) =∑k≥1
P(j es aceptado en la iteración k)
I (j es aceptado en la iteración k ) significa que hay k iteracionesdonde
1. en las k − 1 primeras el algoritmo rechaza2. y en la ultima, la k -esima, Y genera j y el algoritmo lo acepta
P(j aceptado en la iteración k) =
P( algoritmo rechaza k−1 veces )P((Y = j)∧ j es aceptado en la k)
por la independencia de las iteraciones
= P( algoritmo rechaza)k−1 P((Y = j) ∧ j es aceptado)
En una iteración fijaI Probabilidad de que el algoritmo acepte el valor j
P((Y = j) ∧ j es aceptado) = P(j es aceptado | (Y = j))P(Y = j)
=pj
cqjqj
=pj
c
I Probabilidad de que el algoritmo acepte en una iteración
P( el algoritmo acepte) =∑
j
P((Y = j)∧ j es aceptado) =∑
j
pj
c=
1c
P( el algoritmo rechace) = 1− 1c
I G es la variable que mira el número de iteraciones necesarias,entonces G es geométrica de parámetro 1/c.
P(X = j)
P(X = j) = P(j sea aceptado en alguna iteración)
=∞∑
k=1
P(j sea aceptado en la iteración k)
=∞∑
k=1
P( el algoritmo rechaza)k−1 P((Y = j) ∧ j es aceptado)
=∞∑
k=1
(1− 1
c
)k−1 pj
c
= pj
Ejemplo: Método de rechazo
EjemploGenerar una v.a. X con valores en {1,2, . . . ,10} y probabilidades0.11, 0.12, 0.09, 0.08, 0.12, 0.10, 0.09, 0.09, 0.10, 0.10
I Método de la transformada inversa: implica una media (mínima)de 5,04 iteraciones.
I Método de aceptación y rechazo: c = 1.2. La media deiteraciones es 1,2.
Método de Composición
Se tienen métodos eficientes para generar valores de v. a. X1 y X2,con funciones de probabilidad de masa
X1 :{pj j = 0,1, . . . } X2 : {qj j = 0,1, . . . .}
El método de composición permite generar una v.a. X con función deprobabilidad de masa
P(X = j) = αpj + (1− α)qj j = 0,1, . . . , 0 < α < 1
X =
{X1 con probabilidad αX2 con probabilidad 1− α
Método de Composición
Algorithm 2: Algoritmo: Método de composición para dos v.a.Generar U ∼ U(0,1);if U < α then
X ← X1else
X ← X2end
P(X = j) = P(U < α, X1 = j) + P(α < U < 1, X2 = j)= P(U < α)P(X1 = j) + P(α < U < 1)P(X2 = j)= α pj + (1− α)qj
Método de composición
EjemploGenerar X tal que
pj = P(X = j) =
{0.05 para j = 1,2,3,4,50.15 para j = 6,7,8,9,10
(0.05)· 5=0.25(0.15)· 5=0.75
Algorithm 3:Generar U ∼ U(0,1);if U <0.75 then
Generar V ∼ U(0,1);X ← b5Vc+ 6
elseGenerar V ∼ U(0,1);X ← b5Vc+ 1
end
Método de composición
EjemploGenerar X tal que
pj = P(X = j) =
{0.05 para j = 1,2,3,4,50.15 para j = 6,7,8,9,10
(0.05)·10=0.5(0.10)·5=0.5
Algorithm 4: Otra soluciónGenerar U ∼ U(0,1);if U <0.5 then
Generar V ∼ U(0,1);X ← b10Vc+ 1
elseGenerar V ∼ U(0,1);X ← b5Vc+ 6
end
Método de Aceptación y Rechazo
Algunos casos particulares:
I Si Y ∼ U [1,n].I Si X es condicional a Y ≤ n.
I c = maxj{n pj}I c = 1/P(Y ≤ n)
Algorithm 5: ]Y uniforme en [1,n]repeat
GenerarV ∼ U(0,1);Y ← bn VcGenerarU ∼ U(0,1)
until U < n pY/c;X ← Y
Algorithm 6: P(X = j) = P(Y = j | Y ≤ n)
repeatSimular Y
until Y ≤ n;X ← Y
Método de la transformada inversa
X : {x0, x1, . . . }, con P(X = xi) = pi .
Algorithm 7: Transformada InversaF ← p0, i ← 0;Generar U ∼ U(0,1);while U > F do
i ← i + 1;F ← F + pi ;
endX ← xi
I El algoritmo recorre desde un valor en adelante.I Para una v.a. discreta en general, realiza muchas búsquedas.
Veamos algunas alternativas.
Método de la Urna
I X toma un número finito de valores: {x1, x2, . . . , xn}I Cada pi = ki 10−q , con ki entero y q fijo. Esto es:
n∑i=1
ki = 10q
q: es el número máximo de dígitos decimales.I v : un vector de tamaño 10q que contiene ki veces cada
elemento xi .v = x1 . . . x1︸ ︷︷ ︸
k1
x2 . . . x2︸ ︷︷ ︸k2
. . . xn . . . xn︸ ︷︷ ︸kn
Algorithm 8: Algoritmo: Variante AGenerar U ∼ U(0,1);J ← b10qUc+ 1;X ← vJ
Método de la Urna
EjemploX toma valores x1 = 8, x2 = 9, x3 = 10 y x4 = 11, con probabilidadesp1 = 0.2, p2 = 0.1, p3 = 0.4 y p4 = 0.3.
q = 1
p1 = 2 · 10−1, p2 = 1 · 10−1, p3 = 4 · 10−1, p4 = 3 · 10−1.
v = 8 8 9 10 10 10 10 11 11 11
U = 0.378 ⇒ J = 4 ⇒ X ← 10
Método de la Urna
¿Por qué funciona?
P(X = j) = P(k1 + . . . kj−1 < b10qUc ≤ k1 + . . . kj−1 + kj)
=kj
10q = pj
I Desventaja: Necesita 10q lugares de almacenamiento.I Advertencia: Si se redondean los datos para utilizar un q más
chico, recordar que∑
ki debe resultar 1.
Método de la Tabla
Marsaglia (1963) propone la siguiente mejora el método de la urna.I Se utiliza un vector vk , para cada posición decimal:
k = 1,2, . . . ,q.I En vk se almacena xi tantas veces como indique su posición
decimal k -ésima.I Se calcula dk la probabilidad de ocurrencia del dígito de orden k :
dk =suma de los dígitos de orden k en las probabilidades
10k
Método de la Tabla
EjemploSea X con distribución p(1) = 0.15, p(2) = 0.20, p(3) = 0.43,p(4) = 0.22,
v = 1 2 2 3 3 3 3 4 4 m = 9
w = 1 1 1 1 1 3 3 3 4 4 n = 10
d1 =1 + 2 + 4 + 2
10= 0.9 d2 =
5 + 0 + 3 + 2100
= 0.1
Método de la tabla
m = 9n = 10d1 = 0.9d2 = 0.1
Algorithm 10: Método de la tabla (Ejemplo)Input: v , w , m, nGenerar U ∼ U(0,1);if U < 0.9 then
Generar V ∼ U(0,1);J ← bmVc;X ← vJ
elseGenerar V ∼ U(0,1);J ← bnVc;X ← wJ
end
Método de la tabla
¿Por qué funciona el algoritmo?
P(X = 3) = P(X = 3 | elegir decenas)P(elegir decenas)+ P(X = 3 | elegir centenas)P(elegir centenas)
=49
0.9 +310
0.1
= 0.43
I Ventaja sobre el anterior: mucho menor costo dealmacenamiento. (19 lugares en lugar de 100).
I Desventaja: "Mayor" tiempo de ejecución.