De Wikipedia, la enciclopedia libre
El método de aceptación y rechazo es un algoritmo para generar números pseudoaleatorios provenientes de una variable aleatoria .
Descripción [ editar ]
Sea
f
X
(
x
)
{\displaystyle f_{X}(x)}
la función de densidad de la variable aleatoria
X
{\displaystyle X}
, supongamos que existe una función
g
(
x
)
{\displaystyle g(x)}
tal que
g
(
x
)
≥
f
X
(
x
)
{\displaystyle g(x)\geq f_{X}(x)}
∀
x
∈
R
X
{\displaystyle \forall \;x\in R_{X}}
donde
R
X
{\displaystyle R_{X}}
denota el soporte de la variable aleatoria
X
{\displaystyle X}
, como
∫
R
X
f
X
(
x
)
d
x
=
1
{\displaystyle \int _{R_{X}}f_{X}(x)dx=1}
por ser función de densidad entonces
∫
R
X
g
(
x
)
d
x
=
M
≥
1
{\displaystyle \int _{R_{X}}g(x)dx=M\geq 1}
para que
g
(
x
)
{\displaystyle g(x)}
sea una función de densidad, definimos la función
d
(
x
)
:=
g
(
x
)
M
{\displaystyle d(x):={\frac {g(x)}{M}}}
para
x
∈
R
X
{\displaystyle x\in R_{X}}
y
d
(
x
)
=
0
{\displaystyle d(x)=0}
para
x
∉
R
X
{\displaystyle x\notin R_{X}}
.
El método de aceptación y rechazo supone que podemos generar una variable aleatoria
Y
{\displaystyle Y}
con función de densidad
d
{\displaystyle d}
.
El algoritmo para obtener una muestra pseudoaleatoria proveniente de una variable aleatoria
X
{\displaystyle X}
con función de densidad
f
{\displaystyle f}
utilizando una muestra pseudoaleatoria de una variable aleatoria
Y
{\displaystyle Y}
con función de densidad
d
{\displaystyle d}
es el siguiente:
Generar
Y
{\displaystyle Y}
con función de densidad
d
{\displaystyle d}
.
Generar
U
∼
U
(
0
,
1
)
{\displaystyle U\sim \operatorname {U} (0,1)}
independiente de
Y
{\displaystyle Y}
.
Si
U
≤
f
(
Y
)
g
(
Y
)
{\displaystyle U\leq {\frac {f(Y)}{g(Y)}}}
entonces
X
=
Y
{\displaystyle X=Y}
de lo contrario repetir el paso
1
{\displaystyle 1}
.
El algoritmo toma en promedio
M
{\displaystyle M}
iteraciones para obtener una muestra pseudoaleatoria.
Validez del algoritmo [ editar ]
Para demostrar la validez de este algoritmo veamos que
∀
x
∈
R
X
{\displaystyle \forall \;x\in R_{X}}
se verifica
P
[
X
≤
x
]
=
∫
−
∞
x
f
(
y
)
d
y
{\displaystyle \operatorname {P} [X\leq x]=\int _{-\infty }^{x}f(y)dy}
Notemos que
P
[
X
≤
x
]
=
P
[
Y
≤
x
|
U
≤
f
(
Y
)
g
(
Y
)
]
=
P
[
Y
≤
x
,
U
≤
f
(
Y
)
g
(
Y
)
]
P
[
U
≤
f
(
Y
)
g
(
Y
)
]
{\displaystyle {\begin{aligned}\operatorname {P} [X\leq x]&=\operatorname {P} \left[Y\leq x\;{\bigg |}\;U\leq {\frac {f(Y)}{g(Y)}}\right]\\&={\frac {\displaystyle \operatorname {P} \left[Y\leq x\;,\;U\leq {\frac {f(Y)}{g(Y)}}\right]}{\displaystyle \operatorname {P} \left[U\leq {\frac {f(Y)}{g(Y)}}\right]}}\end{aligned}}}
pero
P
[
Y
≤
x
,
U
≤
f
(
Y
)
g
(
Y
)
]
=
∫
−
∞
x
P
[
Y
≤
x
,
U
≤
f
(
Y
)
g
(
Y
)
|
Y
=
y
]
d
(
y
)
d
y
=
∫
−
∞
x
P
[
U
≤
f
(
Y
)
g
(
Y
)
|
Y
=
y
]
g
(
y
)
M
d
y
=
∫
−
∞
x
P
[
U
≤
f
(
y
)
g
(
y
)
]
g
(
y
)
M
d
y
=
∫
−
∞
x
f
(
y
)
g
(
y
)
g
(
y
)
M
d
y
=
1
M
∫
−
∞
x
f
(
y
)
d
y
{\displaystyle {\begin{aligned}\operatorname {P} \left[Y\leq x\;,\;U\leq {\frac {f(Y)}{g(Y)}}\right]&=\int _{-\infty }^{x}\operatorname {P} \left[Y\leq x\;,\;U\leq {\frac {f(Y)}{g(Y)}}\;{\bigg |}\;Y=y\right]d(y)dy\\&=\int _{-\infty }^{x}\operatorname {P} \left[U\leq {\frac {f(Y)}{g(Y)}}\;{\bigg |}\;Y=y\right]{\frac {g(y)}{M}}\;dy\\&=\int _{-\infty }^{x}\operatorname {P} \left[U\leq {\frac {f(y)}{g(y)}}\right]{\frac {g(y)}{M}}\;dy\\&=\int _{-\infty }^{x}{\frac {f(y)}{g(y)}}{\frac {g(y)}{M}}\;dy\\&={\frac {1}{M}}\int _{-\infty }^{x}f(y)dy\end{aligned}}}
y
P
[
U
≤
f
(
Y
)
g
(
Y
)
]
=
∫
R
Y
P
[
U
≤
f
(
Y
)
g
(
Y
)
|
Y
=
y
]
d
(
y
)
d
y
=
∫
R
Y
P
[
U
≤
f
(
y
)
g
(
y
)
]
g
(
y
)
M
d
y
=
∫
R
Y
f
(
y
)
g
(
y
)
g
(
y
)
M
d
y
=
1
M
∫
R
Y
f
(
y
)
d
y
=
1
M
{\displaystyle {\begin{aligned}\operatorname {P} \left[U\leq {\frac {f(Y)}{g(Y)}}\right]&=\int _{R_{Y}}\operatorname {P} \left[U\leq {\frac {f(Y)}{g(Y)}}\;{\bigg |}\;Y=y\right]d(y)dy\\&=\int _{R_{Y}}\operatorname {P} \left[U\leq {\frac {f(y)}{g(y)}}\right]{\frac {g(y)}{M}}\;dy\\&=\int _{R_{Y}}{\frac {f(y)}{g(y)}}{\frac {g(y)}{M}}\;dy\\&={\frac {1}{M}}\int _{R_{Y}}f(y)dy\\&={\frac {1}{M}}\end{aligned}}}
Por lo tanto
P
[
X
≤
x
]
=
P
[
Y
≤
x
,
U
≤
f
(
Y
)
g
(
Y
)
]
P
[
U
≤
f
(
Y
)
g
(
Y
)
]
=
1
M
∫
−
∞
x
f
(
y
)
d
y
1
M
=
∫
−
∞
x
f
(
y
)
d
y
{\displaystyle {\begin{aligned}\operatorname {P} [X\leq x]&={\frac {\operatorname {P} \left[Y\leq x\;,\;U\leq {\frac {f(Y)}{g(Y)}}\right]}{\operatorname {P} \left[U\leq {\frac {f(Y)}{g(Y)}}\right]}}\\&={\frac {\displaystyle {\frac {1}{M}}\int _{-\infty }^{x}f(y)dy}{\displaystyle {\frac {1}{M}}}}\\&=\int _{-\infty }^{x}f(y)dy\end{aligned}}}
Véase también [ editar ]
Referencias [ editar ]
Ross, S.M. (2013). Simulation . Academic Press.
Law, A.M. (2014) Simulation Modeling and Analysis . McGrawHill.