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)\ge f_X(x)$

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

$\underset{R_X}{\int }{f}_X(x)dx=1$

por ser función de densidad entonces

$\underset{R_X}{\int }g(x)dx=M\ge 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 \mathrm{U}(0,1)$ independiente de $Y$.
3. Si $U\le \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 $\mathrm{\forall }x\in R_X$ se verifica

$\mathrm{P}[X\le x]=\underset{-\mathrm{\infty }}{\overset{x}{\int }}f(y)dy$

Notemos que

$\begin{array}{cc}\mathrm{P}[X\le x]& =\mathrm{P}[Y\le x|U\le \frac{f(Y)}{g(Y)}]\\ & =\frac{\mathrm{P}[Y\le x,U\le \frac{f(Y)}{g(Y)}]}{\mathrm{P}[U\le \frac{f(Y)}{g(Y)}]}\end{array}$

pero

$\begin{array}{cc}\mathrm{P}[Y\le x,U\le \frac{f(Y)}{g(Y)}]& =\underset{-\mathrm{\infty }}{\overset{x}{\int }}\mathrm{P}[Y\le x,U\le \frac{f(Y)}{g(Y)}|Y=y]d(y)dy\\ & =\underset{-\mathrm{\infty }}{\overset{x}{\int }}\mathrm{P}[U\le \frac{f(Y)}{g(Y)}|Y=y]\frac{g(y)}{M}dy\\ & =\underset{-\mathrm{\infty }}{\overset{x}{\int }}\mathrm{P}[U\le \frac{f(y)}{g(y)}]\frac{g(y)}{M}dy\\ & =\underset{-\mathrm{\infty }}{\overset{x}{\int }}\frac{f(y)}{g(y)}\frac{g(y)}{M}dy\\ & =\frac{1}{M}\underset{-\mathrm{\infty }}{\overset{x}{\int }}f(y)dy\end{array}$

y

$\begin{array}{cc}\mathrm{P}[U\le \frac{f(Y)}{g(Y)}]& =\underset{R_Y}{\int }\mathrm{P}[U\le \frac{f(Y)}{g(Y)}|Y=y]d(y)dy\\ & =\underset{R_Y}{\int }\mathrm{P}[U\le \frac{f(y)}{g(y)}]\frac{g(y)}{M}dy\\ & =\underset{R_Y}{\int }\frac{f(y)}{g(y)}\frac{g(y)}{M}dy\\ & =\frac{1}{M}\underset{R_Y}{\int }f(y)dy\\ & =\frac{1}{M}\end{array}$

Por lo tanto

$\begin{array}{cc}\mathrm{P}[X\le x]& =\frac{\mathrm{P}[Y\le x,U\le \frac{f(Y)}{g(Y)}]}{\mathrm{P}[U\le \frac{f(Y)}{g(Y)}]}\\ & =\frac{\frac{1}{M}\underset{-\mathrm{\infty }}{\overset{x}{\int }}f(y)dy}{\frac{1}{M}}\\ & =\underset{-\mathrm{\infty }}{\overset{x}{\int }}f(y)dy\end{array}$

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.