El algoritmo Metropolis-Hastings genera una secuencia de muestras aleatorias a partir de una distribución probabilística para la cual el muestreo directo a menudo es difícil.
Se basa en la teoría de la cadena de Markov. La idea clave es construir una cadena de Markov que converja a la distribución dada como su distribución estacionaria. Se pueden aproximar muestras de la distribución estacionaria de una cadena de Markov simulando la cadena de Markov.
Sea [math] \ pi (x) [/ math] la función de masa de probabilidad de la distribución deseada. El desafío es construir una cadena de Markov con probabilidad de transición [matemática] p (x, y) [/ matemática], de modo que [matemática] \ pi (x) [/ matemática] sea su distribución estacionaria.
- ¿Cómo podemos resolver el problema MENOS en SPOJ? Básicamente, ¿cómo hacemos la parte de retroceso para descubrir la secuencia de operaciones?
- ¿Cuáles son algunos algoritmos para el comercio de acciones automatizado?
- ¿Qué significa 'estructuras de datos de dimensión única' en programación?
- En programación de computadoras, ¿por qué es importante la clasificación? ¿Cuándo se utilizan los algoritmos de clasificación en la codificación real?
- ¿La programación a nivel del sistema se ha vuelto obsoleta?
[matemática] p (x, y) [/ matemática] es la probabilidad de transición al estado [matemática] y [/ matemática], dado que el estado actual es [matemática] x [/ matemática].
En general esto requiere
[matemáticas] \ pi (y) = \ sum_x \ pi (x) p (x, y) [/ matemáticas]
Pero aquí usamos una condición más fuerte (llamada reversibilidad de tiempo)
[matemáticas] \ pi (y) p (y, x) = \ pi (x) p (x, y) \ quad \ quad (*) [/ matemáticas]
La segunda condición implica la primera, porque por definición de probabilidad de transición, [matemática] \ sum_x p (y, x) = 1 [/ matemática].
Para encontrar [matemática] p (x, y) [/ matemática] satisfactoria (*), primero proponemos una probabilidad arbitraria de “salto” [matemática] q (x, y) [/ matemática], y luego obtenemos [matemática] p ( x, y) [/ math] al aceptar solo el “salto” con probabilidad [math] \ alpha (x, y) [/ math]. Cuando se rechaza un “salto”, el estado permanece: [matemática] y = x [/ matemática]. Esta idea de “aceptación” no es exclusiva del algoritmo Metropolis-Hastings. Google “muestra de rechazo” para más ejemplos.
Si [math] y = x [/ math], la condición deseada (*) siempre se cumple. Si [math] y \ neq x [/ math], tenemos [math] p (x, y) = q (x, y) \ alpha (x, y) [/ math], y (*) se convierte en:
[matemáticas] \ pi (y) q (y, x) \ alpha (y, x) = \ pi (x) q (x, y) \ alpha (x, y) [/ matemáticas]
es decir,
[matemáticas] \ frac {\ alpha (x, y)} {\ alpha (y, x)} = \ frac {\ pi (y) q (y, x)} {\ pi (x) q (x, y )}[/mates]
Teniendo en cuenta que [math] \ alpha [/ math] toma valores en [0,1], podemos verificar fácilmente que
[matemáticas] \ alpha (x, y) = \ min (\ frac {\ pi (y) q (y, x)} {\ pi (x) q (x, y)}, 1) [/ matemáticas]
Satisface la ecuación anterior. Esto nos da exactamente la probabilidad de aceptación utilizada en el algoritmo Metropolis-Hastings.
(La derivación anterior no pretende ser una prueba. Más bien tiene como objetivo proporcionar una intuición para el algoritmo de Metropolis-Hastings. La discusión asume un espacio de estado discreto, pero la intuición también debe aplicarse al espacio de estado continuo).
