Algoritmo de Metrópolis-Hastings

En estadística y física estadística , el algoritmo de Metropolis-Hastings es un método de Monte Carlo de cadena de Markov (MCMC) para obtener una secuencia de muestras aleatorias de una distribución de probabilidad de la que es difícil obtener un muestreo directo. Las nuevas muestras se añaden a la secuencia en dos pasos: primero se propone una nueva muestra basándose en la anterior; luego, la muestra propuesta se añade a la secuencia o se rechaza según el valor de la distribución de probabilidad en ese punto. La secuencia resultante puede utilizarse para aproximar la distribución (por ejemplo, para generar un histograma ) o para calcular una integral (por ejemplo, un valor esperado ).

Los algoritmos de Metropolis-Hastings y otros algoritmos MCMC se utilizan generalmente para el muestreo de distribuciones multidimensionales, especialmente cuando el número de dimensiones es elevado. Para distribuciones unidimensionales, suelen existir otros métodos (por ejemplo, el muestreo por rechazo adaptativo ) que pueden devolver directamente muestras independientes de la distribución, y estos no presentan el problema de las muestras autocorrelacionadas inherente a los métodos MCMC.

El algoritmo recibe su nombre en parte de Nicholas Metropolis , primer coautor de un artículo de 1953 titulado « Cálculos de la ecuación de estado mediante máquinas de computación rápidas» , junto con Arianna W. Rosenbluth , Marshall Rosenbluth , Augusta H. Teller y Edward Teller . Durante muchos años, el algoritmo se conoció simplemente como el algoritmo de Metropolis . ^{[ 1 ] [ 2 ]} El artículo propuso el algoritmo para el caso de distribuciones de propuesta simétricas, pero en 1970, W. K. Hastings lo extendió al caso más general. ^{[ 3 ]} El método generalizado acabó siendo conocido por ambos nombres, aunque no está claro el origen del término «algoritmo de Metropolis-Hastings».

Existe cierta controversia respecto a la autoría del desarrollo del algoritmo de Metropolis. Metropolis, quien estaba familiarizado con los aspectos computacionales del método, acuñó el término "Monte Carlo" en un artículo anterior con Stanisław Ulam y dirigió el grupo en la División Teórica que diseñó y construyó la computadora MANIAC I utilizada en los experimentos de 1952. Sin embargo, antes de 2003 no existía un relato detallado del desarrollo del algoritmo. Poco antes de su muerte, Marshall Rosenbluth asistió a una conferencia en LANL en 2003 que conmemoraba el 50 aniversario de la publicación de 1953. En esta conferencia, Rosenbluth describió el algoritmo y su desarrollo en una presentación titulada "Génesis del algoritmo de Monte Carlo para mecánica estadística". ^{[ 4 ]} Gubernatis ofrece una aclaración histórica adicional en un artículo de revista de 2005 ^{[ 5 ]} que relata la conferencia del 50 aniversario. Rosenbluth deja claro que él y su esposa Arianna fueron quienes realizaron el trabajo, y que Metropolis no desempeñó ningún papel en el desarrollo más allá de proporcionar tiempo de ordenador.

Esto contradice un relato de Edward Teller, quien afirma en sus memorias que los cinco autores del artículo de 1953 trabajaron juntos durante "días (y noches)". ^{[ 6 ]} En contraste, el relato detallado de Rosenbluth le atribuye a Teller una sugerencia crucial pero temprana de "aprovechar la mecánica estadística y tomar promedios de conjunto en lugar de seguir la cinemática detallada ". Esto, dice Rosenbluth, lo hizo pensar en el enfoque generalizado de Monte Carlo, un tema que dice haber discutido a menudo con John Von Neumann . Arianna Rosenbluth relató (a Gubernatis en 2003) que Augusta Teller comenzó el trabajo informático, pero que Arianna misma lo tomó al mando y escribió el código desde cero. En una historia oral grabada poco antes de su muerte, ^{[ 7 ]} Rosenbluth nuevamente le atribuye a Teller el planteamiento del problema original, a él mismo la resolución y a Arianna la programación de la computadora.

El algoritmo de Metropolis-Hastings puede extraer muestras de cualquier distribución de probabilidad con densidad de probabilidad${\displaystyle P(x)}$, siempre que conozcamos una función${\displaystyle f(x)}$proporcional a la densidad${\displaystyle P}$y los valores de${\displaystyle f(x)}$se puede calcular. El requisito de que${\displaystyle f(x)}$El hecho de que deba ser proporcional a la densidad, en lugar de ser exactamente igual a ella, hace que el algoritmo de Metropolis-Hastings sea particularmente útil, ya que elimina la necesidad de calcular el factor de normalización de la densidad, lo cual suele ser extremadamente difícil en la práctica.

El algoritmo de Metropolis-Hastings genera una secuencia de valores de muestra de tal manera que, a medida que se producen más y más valores de muestra, la distribución de valores se aproxima más a la distribución deseada. Estos valores de muestra se producen iterativamente de tal manera que la distribución de la siguiente muestra depende solo del valor de muestra actual, lo que convierte la secuencia de muestras en una cadena de Markov . Específicamente, en cada iteración, el algoritmo propone un candidato para el siguiente valor de muestra basándose en el valor de muestra actual. Luego, con cierta probabilidad, el candidato es aceptado, en cuyo caso el valor candidato se utiliza en la siguiente iteración, o es rechazado, en cuyo caso el valor candidato se descarta y el valor actual se reutiliza en la siguiente iteración. La probabilidad de aceptación se determina comparando los valores de la función${\displaystyle f(x)}$de los valores de muestra actuales y candidatos con respecto a la distribución deseada.

El método utilizado para proponer nuevos candidatos se caracteriza por la distribución de probabilidad.${\displaystyle g(x\mid y)}$(a veces escrito)${\displaystyle Q(x\mid y)}$) de una nueva muestra propuesta${\displaystyle x}$dada la muestra anterior${\displaystyle y}$Esto se denomina densidad de propuesta , función de propuesta o distribución de salto . Una opción común para${\displaystyle g(x\mid y)}$es una distribución gaussiana centrada en${\displaystyle y}$, de modo que los puntos más cercanos a${\displaystyle y}$es más probable que se visiten a continuación, lo que convierte la secuencia de muestras en un paseo aleatorio gaussiano . En el artículo original de Metropolis et al. (1953),${\displaystyle g(x\mid y)}$Se sugirió que fuera una distribución uniforme limitada a una distancia máxima de${\displaystyle y}$También son posibles funciones de propuesta más complejas, como las de Monte Carlo hamiltoniano , Monte Carlo de Langevin o Crank-Nicolson precondicionado .

A modo de ejemplo, a continuación se describe el algoritmo de Metropolis, un caso especial del algoritmo de Metropolis-Hastings en el que la función propuesta es simétrica.

Algoritmo de Metropolis (distribución de propuestas simétricas)

Dejar${\displaystyle f(x)}$sea ​​una función que sea proporcional a la función de densidad de probabilidad deseada${\displaystyle P(x)}$(también conocida como distribución objetivo). ^{[ a ]}

1. Inicialización: Elija un punto arbitrario${\displaystyle x_{t}}$ser la primera observación en la muestra y elegir una función de propuesta${\displaystyle g(x\mid y)}$. En esta sección,${\displaystyle g}$se supone que es simétrico; en otras palabras debe satisfacer${\displaystyle g(x\mid y)=g(y\mid x)}$.
2. Para cada iteración t :
   • Proponga un candidato${\displaystyle x'}$para la siguiente muestra seleccionando de la distribución${\displaystyle g(x'\mid x_{t})}$.
   • Calcular el índice de aceptación${\displaystyle \alpha =f(x')/f(x_{t})}$, que se utilizará para decidir si se acepta o se rechaza al candidato. ^{[ b ]} Debido a que f es proporcional a la densidad de P , tenemos que${\displaystyle \alpha =f(x')/f(x_{t})=P(x')/P(x_{t})}$.
   • Aceptar o rechazar :
     • Generar un número aleatorio uniforme${\displaystyle u\in [0,1]}$.
     • Si${\displaystyle u\leq \alpha }$, luego acepte al candidato estableciendo${\displaystyle x_{t+1}=x'}$,
     • Si${\displaystyle u>\alpha }$, luego rechazar al candidato y establecer${\displaystyle x_{t+1}=x_{t}}$en cambio.

Este algoritmo procede intentando moverse aleatoriamente por el espacio muestral , a veces aceptando los movimientos y a veces permaneciendo en el mismo lugar.${\displaystyle P(x)}$en un punto específico${\displaystyle x}$es proporcional a las iteraciones que el algoritmo dedica al punto. Nótese que la tasa de aceptación${\displaystyle \alpha }$indica cuán probable es la nueva muestra propuesta con respecto a la muestra actual, según la distribución cuya densidad es${\displaystyle P(x)}$. Si intentamos movernos a un punto que sea más probable que el punto existente (es decir, un punto en una región de mayor densidad de${\displaystyle P(x)}$correspondiente a un${\displaystyle \alpha >1\geq u}$), siempre aceptaremos el movimiento. Sin embargo, si intentamos movernos a un punto menos probable, a veces rechazaremos el movimiento, y cuanto mayor sea la caída relativa en la probabilidad, más probable será que rechacemos el nuevo punto. Por lo tanto, tenderemos a permanecer en (y devolver un gran número de muestras de) regiones de alta densidad de${\displaystyle P(x)}$, mientras que solo ocasionalmente visita regiones de baja densidad. Intuitivamente, esta es la razón por la que este algoritmo funciona y devuelve muestras que siguen la distribución deseada con densidad${\displaystyle P(x)}$.

En comparación con un algoritmo como el muestreo de rechazo adaptativo ^{[ 8 ]} que genera directamente muestras independientes de una distribución, Metropolis-Hastings y otros algoritmos MCMC tienen una serie de desventajas:

• Las muestras están autocorrelacionadas . Aunque a largo plazo sí siguen correctamente${\displaystyle P(x)}$Un conjunto de muestras cercanas estará correlacionado entre sí y no reflejará correctamente la distribución. Esto significa que el tamaño efectivo de la muestra puede ser significativamente menor que el número de muestras tomadas realmente, lo que conlleva grandes errores.
• Aunque la cadena de Markov finalmente converge a la distribución deseada, las muestras iniciales pueden seguir una distribución muy diferente, especialmente si el punto de partida se encuentra en una región de baja densidad. Por consiguiente, suele ser necesario un período de calentamiento ^{[ 9 ]} , durante el cual se descarta un número inicial de muestras.

Por otro lado, la mayoría de los métodos de muestreo por rechazo simples sufren la " maldición de la dimensionalidad ", donde la probabilidad de rechazo aumenta exponencialmente en función del número de dimensiones. El método de Metropolis-Hastings, junto con otros métodos MCMC, no presenta este problema en tal grado y, por lo tanto, suele ser la única solución disponible cuando el número de dimensiones de la distribución a muestrear es elevado. En consecuencia, los métodos MCMC suelen ser los más utilizados para generar muestras a partir de modelos bayesianos jerárquicos y otros modelos estadísticos de alta dimensionalidad empleados actualmente en numerosas disciplinas.

En las distribuciones multivariadas , el algoritmo clásico de Metropolis-Hastings, como se describió anteriormente, implica elegir un nuevo punto de muestra multidimensional. Cuando el número de dimensiones es alto, encontrar la distribución de salto adecuada puede ser difícil, ya que las diferentes dimensiones individuales se comportan de maneras muy distintas, y el ancho de salto (ver arriba) debe ser "justo" para todas las dimensiones a la vez para evitar una mezcla excesivamente lenta. Un enfoque alternativo que suele funcionar mejor en tales situaciones, conocido como muestreo de Gibbs , implica elegir una nueva muestra para cada dimensión por separado de las demás, en lugar de elegir una muestra para todas las dimensiones a la vez. De esa manera, el problema del muestreo de un espacio potencialmente de alta dimensión se reducirá a un conjunto de problemas de muestreo de baja dimensionalidad. ^{[ 10 ]} Esto es especialmente aplicable cuando la distribución multivariada está compuesta por un conjunto de variables aleatorias individuales en las que cada variable está condicionada solo a un pequeño número de otras variables, como es el caso en la mayoría de los modelos jerárquicos típicos . Las variables individuales se muestrean entonces una a una, con cada variable condicionada a los valores más recientes de todas las demás. Se pueden utilizar varios algoritmos para elegir estas muestras individuales, dependiendo de la forma exacta de la distribución multivariada: algunas posibilidades son los métodos de muestreo de rechazo adaptativo , ^{[ 8 ]} el algoritmo de muestreo de Metropolis de rechazo adaptativo, ^{[ 11 ]} un paso de Metropolis-Hastings unidimensional simple o muestreo por rebanadas .

El propósito del algoritmo de Metropolis-Hastings es generar una colección de estados de acuerdo con una distribución deseada.${\displaystyle P(x)}$Para lograr esto, el algoritmo utiliza un proceso de Markov , que alcanza asintóticamente una distribución estacionaria única.${\displaystyle \pi (x)}$de tal manera que${\displaystyle \pi (x)=P(x)}$. ^{[ 12 ]}

Un proceso de Markov se define de forma única por sus probabilidades de transición.${\displaystyle P(x'\mid x)}$, la probabilidad de transición desde cualquier estado dado${\displaystyle x}$a cualquier otro estado determinado${\displaystyle x'}$Tiene una distribución estacionaria única.${\displaystyle \pi (x)}$cuando se cumplen las dos condiciones siguientes: ^{[ 12 ]}

1. Existencia de distribución estacionaria : debe existir una distribución estacionaria.${\displaystyle \pi (x)}$. Una condición suficiente pero no necesaria es el equilibrio detallado , que requiere que cada transición${\displaystyle x\to x'}$es reversible: para cada par de estados${\displaystyle x,x'}$, la probabilidad de estar en estado${\displaystyle x}$y la transición al estado${\displaystyle x'}$debe ser igual a la probabilidad de estar en estado${\displaystyle x'}$y la transición al estado${\displaystyle x}$,${\displaystyle \pi (x)P(x'\mid x)=\pi (x')P(x\mid x')}$.
2. Unicidad de la distribución estacionaria : la distribución estacionaria${\displaystyle \pi (x)}$debe ser único. Esto está garantizado por la ergodicidad del proceso de Markov, que requiere que cada estado debe (1) ser aperiódico: el sistema no regresa al mismo estado en intervalos fijos; y (2) ser recurrente positivo: el número esperado de pasos para regresar al mismo estado es finito.

El algoritmo de Metropolis-Hastings implica diseñar un proceso de Markov (construyendo probabilidades de transición) que cumpla las dos condiciones anteriores, de modo que su distribución estacionaria${\displaystyle \pi (x)}$es elegido para ser${\displaystyle P(x)}$La derivación del algoritmo comienza con la condición de balance detallado :

${\displaystyle P(x'\mid x)P(x)=P(x\mid x')P(x'),}$

que se reescribe como

${\displaystyle {\frac {P(x'\mid x)}{P(x\mid x')}}={\frac {P(x')}{P(x)}}.}$

El enfoque consiste en separar la transición en dos subetapas: la propuesta y la aceptación-rechazo. La distribución de la propuesta${\displaystyle g(x'\mid x)}$es la probabilidad condicional de proponer un estado${\displaystyle x'}$dado${\displaystyle x}$y la distribución de aceptación${\displaystyle A(x',x)}$es la probabilidad de aceptar el estado propuesto${\displaystyle x'}$La probabilidad de transición se puede escribir como el producto de ellas:

${\displaystyle P(x'\mid x)=g(x'\mid x)A(x',x).}$

Insertando esta relación en la ecuación anterior, tenemos

${\displaystyle {\frac {A(x',x)}{A(x,x')}}={\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}.}$

El siguiente paso en la derivación es elegir una razón de aceptación que cumpla la condición anterior. Una opción común es la elección de Metropolis:

${\displaystyle A(x',x)=\min \left(1,{\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}\right).}$

Para esta tasa de aceptación de Metropolis${\displaystyle A}$, cualquiera${\displaystyle A(x',x)=1}$o${\displaystyle A(x,x')=1}$y, en cualquier caso, la condición se cumple.

El algoritmo de Metropolis-Hastings se puede escribir, por lo tanto, de la siguiente manera:

1. Inicializar
   1. Elige un estado inicial${\displaystyle x_{0}}$.
   2. Colocar${\displaystyle t=0}$.
2. Iterar
   1. Generar un estado candidato aleatorio${\displaystyle x'}$de acuerdo a${\displaystyle g(x'\mid x_{t})}$.
   2. Calcular la probabilidad de aceptación${\displaystyle A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)}$.
   3. Aceptar o rechazar :
      1. generar un número aleatorio uniforme${\displaystyle u\in [0,1]}$;
      2. si${\displaystyle u\leq A(x',x_{t})}$, luego acepta el nuevo estado y establece${\displaystyle x_{t+1}=x'}$;
      3. si${\displaystyle u>A(x',x_{t})}$Luego, rechaza el nuevo estado y copia el estado anterior.${\displaystyle x_{t+1}=x_{t}}$.
   4. Incremento : establecer${\displaystyle t=t+1}$.

Siempre que se cumplan las condiciones especificadas, la distribución empírica de estados guardados${\displaystyle x_{0},\ldots ,x_{T}}$se acercará${\displaystyle P(x)}$. El número de iteraciones (${\displaystyle T}$) necesario para estimar eficazmente${\displaystyle P(x)}$depende de la cantidad de factores, incluida la relación entre${\displaystyle P(x)}$y la distribución de la propuesta y la precisión de estimación deseada. ^{[ 13 ]} Para la distribución en espacios de estados discretos, debe ser del orden del tiempo de autocorrelación del proceso de Markov. ^{[ 14 ]} Una explicación accesible de la teoría de convergencia para Metropolis-Hastings se da en. ^{[ 15 ]}

Es importante señalar que no está claro, en un problema general, qué distribución${\displaystyle g(x'\mid x)}$Se debe utilizar o el número de iteraciones necesarias para una estimación adecuada; ambos son parámetros libres del método, que deben ajustarse al problema particular en cuestión.

Un uso común del algoritmo de Metropolis-Hastings es el cálculo de una integral. Específicamente, consideremos un espacio${\displaystyle \Omega \subset \mathbb {R} }$y una distribución de probabilidad${\displaystyle P(x)}$encima${\displaystyle \Omega }$,${\displaystyle x\in \Omega }$. Metropolis-Hastings puede estimar una integral de la forma de

${\displaystyle P(E)=\int _{\Omega }A(x)P(x)\,dx,}$

dónde${\displaystyle A(x)}$es una función (medible) de interés.

Por ejemplo, consideremos una estadística${\displaystyle E(x)}$y su distribución de probabilidad${\displaystyle P(E)}$, que es una distribución marginal . Supongamos que el objetivo es estimar${\displaystyle P(E)}$para${\displaystyle E}$en la cola de${\displaystyle P(E)}$Formalmente,${\displaystyle P(E)}$se puede escribir como

${\displaystyle P(E)=\int _{\Omega }P(E\mid x)P(x)\,dx=\int _{\Omega }\delta {\big (}E-E(x){\big )}P(x)\,dx=E{\big (}P(E\mid X){\big )}}$

y, por lo tanto, estimando${\displaystyle P(E)}$Esto se puede lograr estimando el valor esperado de la función indicadora.${\displaystyle A_{E}(x)\equiv \mathbf {1} _{E}(x)}$, que es 1 cuando${\displaystyle E(x)\in [E,E+\Delta E]}$y cero en caso contrario. Porque${\displaystyle E}$está en la cola de${\displaystyle P(E)}$, la probabilidad de sacar un estado${\displaystyle x}$con${\displaystyle E(x)}$en la cola de${\displaystyle P(E)}$es proporcional a${\displaystyle P(E)}$, que es pequeño por definición. El algoritmo de Metropolis-Hastings se puede utilizar aquí para muestrear estados (raros) más probables y, por lo tanto, aumentar el número de muestras utilizadas para estimar${\displaystyle P(E)}$en las colas. Esto se puede hacer, por ejemplo, utilizando una distribución de muestreo.${\displaystyle \pi (x)}$para favorecer a esos estados (por ejemplo${\displaystyle \pi (x)\propto e^{aE}}$con${\displaystyle a>0}$).

Supongamos que el valor más reciente muestreado es${\displaystyle x_{t}}$Para seguir el algoritmo de Metropolis-Hastings, a continuación dibujamos un nuevo estado de propuesta.${\displaystyle x'}$con densidad de probabilidad${\displaystyle g(x'\mid x_{t})}$y calcular un valor

${\displaystyle a=a_{1}a_{2},}$

dónde

${\displaystyle a_{1}={\frac {P(x')}{P(x_{t})}}}$

es la razón de probabilidad (por ejemplo, posterior bayesiana) entre la muestra propuesta${\displaystyle x'}$y la muestra anterior${\displaystyle x_{t}}$, y

${\displaystyle a_{2}={\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}}$

es la relación de la densidad propuesta en dos direcciones (desde${\displaystyle x_{t}}$a${\displaystyle x'}$y viceversa). Esto es igual a 1 si la densidad de propuesta es simétrica. Entonces el nuevo estado${\displaystyle x_{t+1}}$se elige de acuerdo con las siguientes reglas.

Si${\displaystyle a\geq 1{:}}$

${\displaystyle x_{t+1}=x',}$

demás:

${\displaystyle x_{t+1}={\begin{cases}x'&{\text{with probability }}a,\\x_{t}&{\text{with probability }}1-a.\end{cases}}}$

La cadena de Markov se inicia a partir de un valor inicial arbitrario.${\displaystyle x_{0}}$y el algoritmo se ejecuta durante muchas iteraciones hasta que este estado inicial se "olvida". Estas muestras, que se descartan, se conocen como calentamiento . El conjunto restante de valores aceptados de${\displaystyle x}$representa una muestra de la distribución${\displaystyle P(x)}$.

El algoritmo funciona mejor si la densidad propuesta coincide con la forma de la distribución objetivo.${\displaystyle P(x)}$, de donde es difícil tomar muestras directamente, es decir${\displaystyle g(x'\mid x_{t})\approx P(x')}$. Si una densidad de propuesta gaussiana${\displaystyle g}$Se utiliza el parámetro de varianza.${\displaystyle \sigma ^{2}}$debe ajustarse durante el período de rodaje. Esto generalmente se hace calculando la tasa de aceptación , que es la fracción de muestras propuestas que se acepta en una ventana de los últimos${\displaystyle N}$muestras. La tasa de aceptación deseada depende de la distribución objetivo; sin embargo, se ha demostrado teóricamente que la tasa de aceptación ideal para una distribución gaussiana unidimensional es de aproximadamente el 50%, disminuyendo a aproximadamente el 23% para una${\displaystyle N}$Distribución objetivo gaussiana de dimensión . ^{[ 16 ]} Estas directrices pueden funcionar bien al muestrear a partir de posteriores bayesianos suficientemente regulares, ya que a menudo siguen una distribución normal multivariada , como se puede establecer utilizando el teorema de Bernstein-von Mises . ^{[ 17 ]}

Si${\displaystyle \sigma ^{2}}$es demasiado pequeño, la cadena se mezclará lentamente (es decir, la tasa de aceptación será alta, pero las muestras sucesivas se moverán lentamente por el espacio y la cadena convergerá lentamente a${\displaystyle P(x)}$). Por otro lado, si${\displaystyle \sigma ^{2}}$es demasiado grande, la tasa de aceptación será muy baja porque es probable que las propuestas aterricen en regiones de densidad de probabilidad mucho menor, por lo que${\displaystyle a_{1}}$será muy pequeño, y nuevamente la cadena convergerá muy lentamente. Normalmente se ajusta la distribución de propuestas para que los algoritmos acepten alrededor del 30% de todas las muestras, en consonancia con las estimaciones teóricas mencionadas en el párrafo anterior.

MCMC se puede utilizar para extraer muestras de la distribución posterior de un modelo estadístico . La probabilidad de aceptación viene dada por: ${\displaystyle P_{acc}(\theta _{i}\to \theta ^{*})=\min \left(1,{\frac {{\mathcal {L}}(y|\theta ^{*})P(\theta ^{*})}{{\mathcal {L}}(y|\theta _{i})P(\theta _{i})}}{\frac {Q(\theta _{i}|\theta ^{*})}{Q(\theta ^{*}|\theta _{i})}}\right),}$ dónde${\displaystyle {\mathcal {L}}}$es la probabilidad ,${\displaystyle P(\theta )}$la densidad de probabilidad previa y${\displaystyle Q}$la probabilidad de propuesta (condicional).

• Algoritmos genéticos
• Métodos de partículas de campo medio
• Transporte ligero de la metrópolis
• Metrópolis de múltiples intentos
• Templado paralelo
• Monte Carlo secuencial
• Recocido simulado

• Berg, Bernd A (octubre de 2004). Simulaciones de Monte Carlo de cadenas de Markov y su análisis estadístico: con código Fortran basado en la web . World Scientific . doi : 10.1142/5602 . ISBN 978-981-238-935-0.
• Chib, Siddhartha; Greenberg, Edward (noviembre de 1995). "Comprendiendo el algoritmo de Metropolis-Hastings" . The American Statistician . 49 (4): 327. doi : 10.2307/2684568 .
• Minh, David DL; Minh, Do Le (Paul) (2015-02-07). "Understanding the Hastings Algorithm" . Communications in Statistics - Simulation and Computation . 44 (2): 332– 349. arXiv : 1408.4438 . doi : 10.1080/03610918.2013.777455 . ISSN 0361-0918 . 
• Bolstad, William M. (2010). Comprensión de la estadística bayesiana computacional . Serie Wiley en estadística computacional. Hoboken, NJ: Wiley. ISBN 978-0-470-04609-8.