Método de aceptación y rechazo

El método de aceptación y rechazo es un algoritmo para generar números pseudoaleatorios provenientes de una variable aleatoria.

Descripción

Sea $f_{X}(x)$ la función de densidad de la variable aleatoria $X$, supongamos que existe una función $g(x)$ tal que

$g(x)\geq f_{X}(x)$

$\forall \;x\in R_{X}$ donde $R_{X}$ denota el soporte de la variable aleatoria $X$, como

$\int _{R_{X}}f_{X}(x)dx=1$

por ser función de densidad entonces

$\int _{R_{X}}g(x)dx=M\geq 1$

para que $g(x)$ sea una función de densidad, definimos la función

$d(x):={\frac {g(x)}{M}}$

para $x\in R_{X}$ y $d(x)=0$ para $x\notin R_{X}$.

El método de aceptación y rechazo supone que podemos generar una variable aleatoria $Y$ con función de densidad $d$.

Algoritmo

El algoritmo para obtener una muestra pseudoaleatoria proveniente de una variable aleatoria $X$ con función de densidad $f$ utilizando una muestra pseudoaleatoria de una variable aleatoria $Y$ con función de densidad $d$ es el siguiente:

1. Generar $Y$ con función de densidad $d$.
2. Generar $U\sim \operatorname {U} (0,1)$ independiente de $Y$.
3. Si $U\leq {\frac {f(Y)}{g(Y)}}$ entonces $X=Y$ de lo contrario repetir el paso $1$.

El algoritmo toma en promedio $M$ iteraciones para obtener una muestra pseudoaleatoria.

Validez del algoritmo

Para demostrar la validez de este algoritmo veamos que $\forall \;x\in R_{X}$ se verifica

$\operatorname {P} [X\leq x]=\int _{-\infty }^{x}f(y)dy$

Notemos que

${\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

${\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

${\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

${\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

• Método de la transformada inversa
• Número pseudoaleatorio
• Generador lineal congruencial

Referencias

• Ross, S.M. (2013). Simulation. Academic Press.
• Law, A.M. (2014) Simulation Modeling and Analysis. McGrawHill.

• Datos: Q109424341