Muestreo de rechazo

En análisis numérico y estadística computacional , el muestreo por rechazo es una técnica básica utilizada para generar observaciones a partir de una distribución . También se le conoce comúnmente como método de aceptación-rechazo o "algoritmo de aceptación-rechazo" y es un tipo de método de simulación exacta. El método funciona para cualquier distribución en${\displaystyle \mathbb {R} ^{m}}$con una densidad .

El muestreo por rechazo se basa en la observación de que, para muestrear una variable aleatoria en una dimensión, se puede realizar un muestreo aleatorio uniforme del grafo cartesiano bidimensional y conservar las muestras en la región bajo el grafo de su función de densidad. ^{[ 1 ] [ 2 ] [ 3 ]} Cabe señalar que esta propiedad puede extenderse a funciones de N dimensiones.

El algoritmo, que fue utilizado por John von Neumann ^{[ 4 ]} y se remonta a Buffon y su aguja , extrae una muestra de una función de densidad de probabilidad (objetivo).${\displaystyle f(x)}$, que es proporcional a${\displaystyle f_{\varpropto }(x)}$, utilizando extracciones de una densidad de probabilidad (de propuesta) más simple${\displaystyle g(x)}$como sigue:

Muestreo por rechazo

Aporte

Densidad objetivo${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$, densidad de la propuesta${\displaystyle g(x)}$, constante${\displaystyle M}$de tal manera que${\displaystyle f_{\varpropto }(x)\leq Mg(x)}$a pesar de${\displaystyle x}$.

Algoritmo

1. Muestra${\displaystyle X\sim g(x)}$
2. Muestra${\displaystyle U\sim \mathrm {Unif} (0,1)}$, independientemente de${\displaystyle X}$.
3. Calcular la razón de verosimilitud${\displaystyle W={\dfrac {f_{\varpropto }(X)}{g(X)}}}$.
4. Si${\displaystyle W<M\times U}$, rechazar${\displaystyle X}$y repita desde el paso 1. De lo contrario, acepte y muestre la salida.${\displaystyle X}$.

Producción

Una muestra${\displaystyle X}$extraído de${\displaystyle f}$.

El algoritmo tomará un promedio de${\displaystyle {\frac {M}{\int f_{\varpropto }(y)dy}}}$rechazos para obtener una muestra.

Para visualizar la motivación detrás del muestreo por rechazo, imagine graficar la función de densidad de probabilidad (FDP) de una variable aleatoria en un tablero rectangular grande y lanzar dardos hacia él. Suponga que los dardos están distribuidos uniformemente alrededor del tablero. Ahora retire todos los dardos que están fuera del área bajo la curva. Los dardos restantes estarán distribuidos uniformemente dentro del área bajo la curva, y la${\displaystyle x}$Las posiciones de estos dardos se distribuirán según la densidad de la variable aleatoria. Esto se debe a que hay más posibilidades de que los dardos aterricen donde la curva es más pronunciada y, por lo tanto, la densidad de probabilidad es mayor.

La visualización que acabamos de describir es equivalente a una forma particular de muestreo por rechazo donde la "distribución de propuestas" es uniforme. Por lo tanto, su gráfico es un rectángulo. La forma general del muestreo por rechazo supone que el tablero no es necesariamente rectangular, sino que tiene forma según la densidad de alguna distribución de propuestas (no necesariamente normalizada a${\displaystyle 1}$) de la que sabemos cómo muestrear (por ejemplo, usando muestreo por inversión ). Su forma debe ser al menos tan alta en cada punto como la distribución de la que queremos muestrear, de modo que la primera encierre completamente a la segunda. De lo contrario, habría partes del área curva de la que queremos muestrear que nunca se podrían alcanzar.

El muestreo por rechazo funciona de la siguiente manera:

1. Muestra un punto en el${\displaystyle x}$-eje de la distribución de la propuesta.
2. Dibuja una línea vertical en este punto.${\displaystyle x}$-posición, hasta el valor y de la función de densidad de probabilidad de la distribución propuesta.
3. Muestre uniformemente a lo largo de esta línea. Si el valor muestreado es mayor que el valor de la distribución deseada en esta línea vertical, rechace la${\displaystyle x}$-valor y volver al paso 1; de lo contrario,${\displaystyle x}$-valor es una muestra de la distribución deseada.

Este algoritmo se puede utilizar para muestrear el área bajo cualquier curva, independientemente de si la función integra a 1. De hecho, escalar una función por una constante no tiene efecto sobre el área muestreada.${\displaystyle x}$-posiciones . Por lo tanto, el algoritmo se puede utilizar para muestrear de una distribución cuya constante de normalización es desconocida, lo cual es común en estadística computacional .

En el siguiente análisis asumimos, por simplicidad, que ${\displaystyle f\equiv f_{\varpropto }}$El método de muestreo por rechazo genera valores de muestreo a partir de una distribución objetivo con función de densidad de probabilidad${\displaystyle f(x)}$mediante el uso de una distribución de propuesta con densidad de probabilidad${\displaystyle g(x)}$La idea es que se puede generar un valor de muestra a partir de${\displaystyle f}$en su lugar, tomando muestras de${\displaystyle g}$y aceptando la muestra de${\displaystyle f}$con probabilidad${\displaystyle f(x)/(Mg(x))}$, repitiendo los sorteos de${\displaystyle g}$hasta que se acepte un valor. ${\displaystyle M}$Aquí hay una cota constante y finita para la razón de verosimilitud.${\displaystyle f(x)/g(x)}$, satisfactorio${\displaystyle M<\infty }$sobre el apoyo de${\displaystyle f}$; en otras palabras,${\displaystyle M}$debe satisfacer${\displaystyle f(x)\leq Mg(x)}$para todos los valores de${\displaystyle x}$. Tenga en cuenta que esto requiere el apoyo de${\displaystyle g}$debe incluir el apoyo de${\displaystyle f}$-en otras palabras,${\displaystyle g(x)>0}$cuando sea${\displaystyle f(x)>0}$.

La validación de este método es el principio de envolvente: al simular el par${\textstyle (x,v=u\cdot Mg(x))}$, se produce una simulación uniforme sobre el subgrafo de${\textstyle Mg(x)}$. Aceptar únicamente pares tales que${\textstyle u<f(x)/(Mg(x))}$luego produce pares${\displaystyle (x,v)}$distribuidos uniformemente sobre el subgrafo de${\displaystyle f(x)}$y por lo tanto, marginalmente, una simulación de${\displaystyle f(x).}$

Esto significa que, con suficientes réplicas, el algoritmo genera una muestra de la distribución deseada.${\displaystyle f(x)}$Existen varias extensiones de este algoritmo, como el algoritmo de Metropolis .

Este método se relaciona con el campo general de las técnicas de Monte Carlo , incluidos los algoritmos de Monte Carlo de cadena de Markov que también utilizan una distribución proxy para lograr la simulación a partir de la distribución objetivo.${\displaystyle f(x)}$Constituye la base de algoritmos como el algoritmo de Metropolis .

La probabilidad de aceptación incondicional es la proporción de muestras propuestas que son aceptadas, que es$${\displaystyle {\begin{aligned}\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)&=\operatorname {E} \mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}\\[6pt]&=\operatorname {E} \left[\operatorname {E} [\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}|Y]\right]&{\text{(by tower property)}}\\[6pt]&=\operatorname {E} \left[\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}{\biggr |}Y\right)\right]\\[6pt]&=\operatorname {E} \left[{\frac {f(Y)}{Mg(Y)}}\right]&({\text{because }}\Pr(U\leq u)=u,{\text{when }}U{\text{ is uniform on }}(0,1))\\[6pt]&=\int \limits _{y:g(y)>0}{\frac {f(y)}{Mg(y)}}g(y)\,dy\\[6pt]&={\frac {1}{M}}\int \limits _{y:g(y)>0}f(y)\,dy\\[6pt]&={\frac {1}{M}}&({\text{since support of }}Y{\text{ includes support of }}X)\end{aligned}}}$$dónde${\displaystyle U\sim \mathrm {Unif} (0,1)}$y el valor de${\displaystyle Y}$Cada vez se genera bajo la función de densidad${\displaystyle g(\cdot )}$de la distribución de la propuesta.

El número de muestras requeridas de${\displaystyle g}$Para obtener un valor aceptado, sigue una distribución geométrica con probabilidad${\displaystyle 1/M}$, que tiene significado${\displaystyle M}$Intuitivamente,${\displaystyle M}$es el número esperado de iteraciones necesarias, como medida de la complejidad computacional del algoritmo.

Reescribe la ecuación anterior,$${\displaystyle M={\frac {1}{\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}}}$$ Tenga en cuenta que${\textstyle 1\leq M<\infty }$, debido a la fórmula anterior, donde${\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}$es una probabilidad que solo puede tomar valores en el intervalo${\displaystyle [0,1]}$. Cuando${\displaystyle M}$cuanto más cercano a uno sea elegido, mayor será la probabilidad de aceptación incondicional cuanto menos varíe esa relación, ya que${\displaystyle M}$es el límite superior para la razón de verosimilitud${\textstyle f(x)/g(x)}$. En la práctica, un valor de${\displaystyle M}$Se prefiere un valor más cercano a 1, ya que implica menos muestras rechazadas, en promedio, y por lo tanto menos iteraciones del algoritmo. En este sentido, se prefiere tener${\displaystyle M}$lo más pequeño posible (sin dejar de ser satisfactorio)${\displaystyle f(x)\leq Mg(x)}$, lo que sugiere que${\displaystyle g(x)}$En general debería parecerse a${\displaystyle f(x)}$de alguna manera. Sin embargo, tenga en cuenta que${\displaystyle M}$no puede ser igual a 1: tal implicaría que${\displaystyle f(x)=g(x)}$, es decir, que las distribuciones objetivo y propuesta son en realidad la misma distribución.

El muestreo por rechazo se utiliza con mayor frecuencia en casos donde la forma de${\displaystyle f(x)}$dificulta el muestreo. Una sola iteración del algoritmo de rechazo requiere muestrear de la distribución de propuestas, extraer de una distribución uniforme y evaluar la${\displaystyle f(x)/(Mg(x))}$expresión. Por lo tanto, el muestreo por rechazo es más eficiente que algún otro método siempre que${\displaystyle M}$veces el costo de estas operaciones —que es el costo esperado de obtener una muestra con muestreo por rechazo— es menor que el costo de obtener una muestra utilizando el otro método.

El muestreo por rechazo puede ser mucho más eficiente en comparación con los métodos ingenuos en algunas situaciones. Por ejemplo, dado un problema como el muestreo${\textstyle X\sim F(\cdot )}$condicionalmente en${\displaystyle X}$dado el conjunto${\displaystyle A}$, es decir,${\textstyle X|X\in A}$, a veces${\textstyle X}$se puede simular fácilmente utilizando métodos ingenuos (por ejemplo, mediante muestreo de transformada inversa ):

• Muestra${\textstyle X\sim F(\cdot )}$de forma independiente y aceptar aquellos que sean satisfactorios.${\displaystyle \{n\geq 1:X_{n}\in A\}}$
• Producción:${\displaystyle \{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}}$(véase también truncamiento (estadística) )

El problema es que este muestreo puede ser difícil e ineficiente, si${\textstyle \mathbb {P} (X\in A)\approx 0}$El número esperado de iteraciones sería${\displaystyle {\frac {1}{\mathbb {P} (X\in A)}}}$, que podría estar cerca del infinito. Además, incluso cuando se aplica el método de muestreo por rechazo, siempre es difícil optimizar el límite.${\displaystyle M}$para la razón de verosimilitud. La mayoría de las veces,${\displaystyle M}$es grande y la tasa de rechazo es alta, el algoritmo puede ser muy ineficiente. La familia exponencial natural (si existe), también conocida como inclinación exponencial, proporciona una clase de distribuciones de propuestas que pueden reducir la complejidad computacional, el valor de${\displaystyle M}$y acelerar los cálculos (véanse ejemplos: trabajar con familias exponenciales naturales).

Dada una variable aleatoria${\displaystyle X\sim F(\cdot )}$,${\displaystyle F(x)=\mathbb {P} (X\leq x)}$es la distribución objetivo. Supongamos, para simplificar, que la función de densidad se puede escribir explícitamente como${\displaystyle f(x)}$. Elija la propuesta como

$${\displaystyle {\begin{aligned}F_{\theta }(x)&=\mathbb {E} \left[\exp(\theta X-\psi (\theta ))\mathbb {I} (X\leq x)\right]\\&=\int _{-\infty }^{x}e^{\theta y-\psi (\theta )}f(y)dy\\g_{\theta }(x)&=F'_{\theta }(x)=e^{\theta x-\psi (\theta )}f(x)\end{aligned}}}$$

dónde${\displaystyle \psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)}$y${\displaystyle \Theta =\{\theta$ :\psi (\theta )<\infty \}} . Claramente,${\displaystyle \{F_{\theta }(\cdot )\}_{\theta \in \Theta }}$, pertenece a una familia exponencial natural . Además, la razón de verosimilitud es

$${\displaystyle Z(x)={\frac {f(x)}{g_{\theta }(x)}}={\frac {f(x)}{e^{\theta x-\psi (\theta )}f(x)}}=e^{-\theta x+\psi (\theta )}}$$

Tenga en cuenta que${\displaystyle \psi (\theta )<\infty }$implica que de hecho es una función de generación de cumulantes , es decir,

${\displaystyle \psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }}$.

Es fácil derivar la función de generación de cumulantes de la propuesta y, por lo tanto, los cumulantes de la propuesta.

${\displaystyle {\begin{aligned}\psi _{\theta }(\eta )&=\log \left(\mathbb {E} _{\theta }\exp(\eta X)\right)=\psi (\theta +\eta )-\psi (\theta )<\infty \\\mathbb {E} _{\theta }(X)&=\left.{\frac {\partial \psi _{\theta }(\eta )}{\partial \eta }}\right|_{\eta =0}\\\mathrm {Var} _{\theta }(X)&=\left.{\frac {\partial ^{2}\psi _{\theta }(\eta )}{\partial ^{2}\eta }}\right|_{\eta =0}\end{aligned}}}$

Como ejemplo sencillo, supongamos que bajo${\displaystyle F(\cdot )}$,${\displaystyle X\sim \mathrm {N} (\mu ,\sigma ^{2})}$, con${\textstyle \psi (\theta )=\mu \theta +{\frac {\sigma ^{2}\theta ^{2}}{2}}}$El objetivo es tomar muestras.${\displaystyle X|X\in \left[b,\infty \right]}$, dónde${\displaystyle b>\mu }$El análisis se desarrolla de la siguiente manera:

• Elija el formato de distribución de la propuesta.${\displaystyle F_{\theta }(\cdot )}$, con función generadora de cumulantes como

${\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\theta )=(\mu +\theta \sigma ^{2})\eta +{\frac {\sigma ^{2}\eta ^{2}}{2}}}$,

lo que implica además que se trata de una distribución normal.${\displaystyle \mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})}$.

• Decide lo bien elegido${\displaystyle \theta ^{*}}$para la distribución de la propuesta. En esta configuración, la forma intuitiva de elegir${\displaystyle \theta ^{*}}$es establecer

${\displaystyle \mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b}$,

eso es${\displaystyle \theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}.}$La distribución de la propuesta es, por lo tanto,${\displaystyle g_{\theta ^{*}}(x)=\mathrm {N} (b,\sigma ^{2})}$.

• Escriba explícitamente el objetivo, la propuesta y la razón de verosimilitud.

$${\displaystyle {\begin{aligned}f_{X|X\geq b}(x)&={\frac {f(x)\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\\g_{\theta ^{*}}(x)&=f(x)\exp(\theta ^{*}x-\psi (\theta ^{*}))\\Z(x)&={\frac {f_{X|X\geq b}(x)}{g_{\theta ^{*}}(x)}}={\frac {\exp(-\theta ^{*}x+\psi (\theta ^{*}))\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\end{aligned}}}$$

• Deriva el límite${\displaystyle M}$para la razón de verosimilitud${\displaystyle Z(x)}$, que es una función decreciente para${\displaystyle x\in [b,\infty ]}$, por lo tanto

$${\displaystyle M=Z(b)={\frac {\exp(-\theta ^{*}b+\psi (\theta ^{*}))}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} \left(\mathrm {N} (0,1)\geq {\frac {b-\mu }{\sigma }}\right)}}}$$

• Criterio de muestreo de rechazo: para${\displaystyle U\sim \mathrm {Unif} (0,1)}$, si

$${\displaystyle U\leq {\frac {Z(x)}{M}}=e^{-\theta ^{*}(x-b)}\mathbb {I} (x\geq b)}$$

sostiene, acepta el valor de${\displaystyle X}$; si no, continúe muestreando nuevos${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$y nuevo${\textstyle U\sim \mathrm {Unif} (0,1)}$hasta la aceptación.

Para el ejemplo anterior, como medida de la eficiencia, el número esperado de iteraciones del método de muestreo por rechazo basado en la familia exponencial natural es de orden${\displaystyle b}$, eso es${\displaystyle M(b)=O(b)}$, mientras que bajo el método ingenuo, el número esperado de iteraciones es${\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}$, lo cual es mucho más ineficiente.

En general, la inclinación exponencial, una clase paramétrica de distribución de propuestas, resuelve los problemas de optimización de manera conveniente, con sus útiles propiedades que caracterizan directamente la distribución de la propuesta. Para este tipo de problema, simular${\displaystyle X}$condicionalmente en${\displaystyle X\in A}$Dentro de la clase de distribuciones simples, la clave está en utilizar la familia exponencial natural, que ayuda a controlar la complejidad y a acelerar considerablemente el cálculo. De hecho, existen razones matemáticas profundas para usar la familia exponencial natural.

El muestreo por rechazo requiere conocer la distribución objetivo (específicamente, la capacidad de evaluar la función de densidad de probabilidad objetivo en cualquier punto).

El muestreo por rechazo puede generar muchas muestras no deseadas si la función muestreada está muy concentrada en una región específica, por ejemplo, una función con un pico en algún punto. Para muchas distribuciones, este problema se puede resolver mediante una extensión adaptativa (véase muestreo por rechazo adaptativo ) o con un cambio de variables apropiado mediante el método de la razón de uniformes . Además, a medida que aumenta la dimensión del problema, la relación entre el volumen incrustado y los "bordes" del volumen de incrustación tiende a cero, lo que puede provocar muchos rechazos antes de generar una muestra útil, haciendo que el algoritmo sea ineficiente e impráctico. Véase maldición de la dimensionalidad . En dimensiones elevadas, es necesario utilizar un enfoque diferente, generalmente un método de Monte Carlo de cadena de Markov, como el muestreo de Metropolis o el muestreo de Gibbs . (Sin embargo, el muestreo de Gibbs, que descompone un problema de muestreo multidimensional en una serie de muestras de baja dimensión, puede utilizar el muestreo por rechazo como uno de sus pasos).

Cuando no hay constante finita${\displaystyle M}$satisfaciendo la condición${\displaystyle M\geq \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$ existe, o un finito adecuado${\displaystyle M<\infty }$Es simplemente demasiado difícil de calcular, pero aún se puede utilizar una versión modificada del algoritmo de muestreo por rechazo para simular (aproximadamente) a partir del objetivo.${\displaystyle f}$, como sigue. ^{[ 5 ]}

Muestreo de rechazo regenerativo

Aporte

Densidad objetivo${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$, densidad de la propuesta${\displaystyle g(x)}$, gran constante ${\displaystyle M}$.

Algoritmo

Establecer contador${\displaystyle t\leftarrow 0}$.

1. Muestra${\displaystyle X\sim g(x)}$y aumento${\displaystyle t\leftarrow t+1}$.
2. Calcular la razón de verosimilitud${\displaystyle W_{t}={\dfrac {f_{\varpropto }(X)}{g(X)}}}$.
3. Si${\displaystyle W_{1}+\cdots +W_{t}<M}$, rechazar${\displaystyle X}$y repita desde el paso 1. De lo contrario, acepte y muestre la salida.${\displaystyle X}$.

Producción

Una muestra${\displaystyle X}$aproximadamente extraído de${\displaystyle f}$.

La única diferencia entre la versión regenerativa anterior y el muestreo de rechazo clásico es que la decisión de aceptación se basa en si la suma acumulativa de todas las razones de verosimilitud${\displaystyle W_{1}+\cdots +W_{t}}$supera${\displaystyle M}$(eso es,${\displaystyle W_{1}+\cdots +W_{t}>M}$), en lugar de basarse en si la razón de verosimilitud actual${\displaystyle W_{t}}$supera${\displaystyle M\times U}$(eso es,${\displaystyle W_{t}>M\times U}$).

Se puede demostrar que, como${\displaystyle M\rightarrow \infty }$, la variable de salida del algoritmo ${\displaystyle X=X_{M}}$converge en distribución hacia el objetivo deseado con densidad${\displaystyle f}$. ^{[ 5 ]}

Otro enfoque que no requiere conocimiento de la constante límite óptima ${\displaystyle \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$es el método de muestreo de rechazo supremo empírico . ^{[ 6 ]}

Para muchas distribuciones, encontrar una distribución propuesta que incluya la distribución dada sin desperdiciar mucho espacio es difícil. Una extensión del muestreo por rechazo que puede utilizarse para superar esta dificultad y muestrear de manera eficiente a partir de una amplia variedad de distribuciones (siempre que tengan funciones de densidad logarítmicamente cóncavas , lo cual es el caso de la mayoría de las distribuciones comunes, incluso aquellas cuyas funciones de densidad no son cóncavas) se conoce como muestreo por rechazo adaptativo (ARS) .

Hay tres ideas básicas en esta técnica tal como fue introducida finalmente por Gilks ​​en 1992: ^{[ 7 ]}

1. Si le sirve de ayuda, defina la distribución de su envolvente en espacio logarítmico (por ejemplo, probabilidad logarítmica o densidad logarítmica). Es decir, trabaje con${\displaystyle h\left(x\right)=\log g\left(x\right)}$en lugar de${\displaystyle g\left(x\right)}$directamente.
   • A menudo, las distribuciones que tienen funciones de densidad algebraicamente desordenadas tienen funciones de densidad logarítmica razonablemente más simples (es decir, cuando${\displaystyle f\left(x\right)}$es desordenado,${\displaystyle \log f\left(x\right)}$puede ser más fácil trabajar con él o, al menos, estar más cerca de ser lineal por partes).
2. En lugar de una única función de densidad de envolvente uniforme, utilice una función de densidad lineal por tramos como envolvente.
   • Cada vez que tenga que rechazar una muestra, puede utilizar el valor de${\displaystyle f\left(x\right)}$que usted evaluó, para mejorar la aproximación por partes${\displaystyle h\left(x\right)}$Esto reduce, por lo tanto, la probabilidad de que su próximo intento sea rechazado. Asintóticamente, la probabilidad de tener que rechazar su muestra debería converger a cero y, en la práctica, suele hacerlo muy rápidamente.
   • Tal como se propone, cada vez que elegimos un punto que es rechazado, ajustamos la envolvente con otro segmento de línea que es tangente a la curva en el punto con la misma coordenada x que el punto elegido.
   • Un modelo lineal por partes de la distribución logarítmica propuesta da como resultado un conjunto de distribuciones exponenciales por partes (es decir, segmentos de una o más distribuciones exponenciales, unidos extremo con extremo). Las distribuciones exponenciales se comportan bien y se comprenden bien. El logaritmo de una distribución exponencial es una línea recta, por lo que este método consiste esencialmente en encerrar el logaritmo de la densidad dentro de una serie de segmentos de línea. Esta es la fuente de la restricción de concavidad logarítmica: si una distribución es logarítmicamente cóncava, entonces su logaritmo es cóncavo (con forma de U invertida), lo que significa que un segmento de línea tangente a la curva siempre pasará por encima de ella.
   • Si no se trabaja en el espacio logarítmico, también se puede muestrear una función de densidad lineal por partes mediante distribuciones triangulares ^{[ 8 ].}
3. Podemos aprovechar aún más el requisito de concavidad (logarítmica), para potencialmente evitar el costo de evaluar${\displaystyle f\left(x\right)}$cuando su muestra sea aceptada.
   • Así como podemos construir una cota superior lineal por partes (la función "envolvente") utilizando los valores de${\displaystyle h\left(x\right)}$que tuvimos que evaluar en la cadena actual de rechazos, también podemos construir una cota inferior lineal por partes (la función de "compresión") utilizando también estos valores.
   • Antes de evaluar (el potencialmente costoso)${\displaystyle f\left(x\right)}$Para ver si su muestra será aceptada, es posible que ya sepamos si será aceptada comparándola con la (idealmente más barata).${\displaystyle g_{l}\left(x\right)}$(o${\displaystyle h_{l}\left(x\right)}$en este caso) función de compresión que tienen disponible.
   • Este paso de compresión es opcional, incluso cuando lo sugiere Gilks. En el mejor de los casos, solo evita una evaluación adicional de la densidad objetivo (que suele ser compleja y/o costosa). Sin embargo, presumiblemente para funciones de densidad particularmente costosas (y suponiendo una rápida convergencia de la tasa de rechazo hacia cero), esto puede marcar una diferencia considerable en el tiempo de ejecución final.

El método consiste esencialmente en determinar sucesivamente una envolvente de segmentos de línea recta que se aproxime cada vez mejor al logaritmo, manteniéndose siempre por encima de la curva, partiendo de un número fijo de segmentos (posiblemente una sola línea tangente). El muestreo de una variable aleatoria exponencial truncada es sencillo. Basta con tomar el logaritmo de una variable aleatoria uniforme (con el intervalo y la truncación adecuados).

Desafortunadamente, ARS solo se puede aplicar para el muestreo de densidades objetivo log-cóncavas. Por esta razón, se han propuesto varias extensiones de ARS en la literatura para abordar distribuciones objetivo no log-cóncavas. ^{[ 9 ] [ 10 ] [ 11 ]} Además, se han diseñado diferentes combinaciones de ARS y el método de Metropolis-Hastings para obtener un muestreador universal que construye densidades de propuesta autoajustables (es decir, una propuesta construida y adaptada automáticamente al objetivo). Esta clase de métodos a menudo se denomina algoritmos de muestreo de Metropolis de rechazo adaptativo (ARMS) . ^{[ 12 ] [ 13 ]} Las técnicas adaptativas resultantes siempre se pueden aplicar, pero las muestras generadas están correlacionadas en este caso (aunque la correlación se desvanece rápidamente a cero a medida que aumenta el número de iteraciones).

• Muestreo de transformada inversa
• Relación de uniformes
• Muestreo de números pseudoaleatorios
• Algoritmo de zigurat

• Robert, CP; Casella, G. (2004). Métodos estadísticos de Monte Carlo (Segunda  edición). Nueva York: Springer-Verlag.