Acoplamiento del pasado

Entre los algoritmos Monte Carlo de la cadena de Markov (MCMC) , el acoplamiento del pasado es un método para muestrear la distribución estacionaria de una cadena de Markov . A diferencia de muchos algoritmos MCMC, el acoplamiento del pasado proporciona en principio una muestra perfecta de la distribución estacionaria . Fue inventado por James Propp y David Wilson en 1996.

la idea basica

Considere una cadena de Markov aperiódica irreducible de estado finito con espacio de estados y distribución estacionaria (única) ( es un vector de probabilidad). Supongamos que llegamos a una distribución de probabilidad en el conjunto de mapas con la propiedad de que para cada fijo , su imagen se distribuye de acuerdo con la probabilidad de transición de from state . Un ejemplo de tal distribución de probabilidad es aquella en la que es independiente de cuando sea , pero a menudo vale la pena considerar otras distribuciones. Ahora seamos muestras independientes de . ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle \mu }$ ${\displaystyle f:S\to S}$ ${\displaystyle s\in S}$ ${\displaystyle f(s)}$ ${\displaystyle M}$ ${\displaystyle s}$ ${\displaystyle f(s)}$ ${\displaystyle f(s')}$ ${\displaystyle s\neq s'}$ ${\displaystyle f_{j}}$ ${\displaystyle j\in \mathbb {Z} }$ ${\displaystyle \mu }$

Supongamos que se elige aleatoriamente según la secuencia y es independiente de ella . (No nos preocupamos por ahora de dónde viene esto.) Entonces también se distribuye de acuerdo con , porque es -estacionario y nuestra suposición sobre la ley de . Definir ${\displaystyle x}$ ${\displaystyle \pi }$ ${\displaystyle f_{j}}$ ${\displaystyle x}$ ${\displaystyle f_{-1}(x)}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle M}$ ${\displaystyle f}$

${\displaystyle F_{j}:=f_{-1}\circ f_{-2}\circ \cdots \circ f_{-j}.}$

Luego sigue por inducción que también se distribuye según para cada . Sin embargo, puede ocurrir que para algunos la imagen del mapa sea un solo elemento . En otras palabras, para cada . Por lo tanto, no necesitamos tener acceso para poder calcular . Luego, el algoritmo implica encontrar algo que sea un singleton y generar el elemento de ese singleton. El diseño de una buena distribución para la cual la tarea de encontrarla y computarla no sea demasiado costosa no siempre es obvio, pero se ha logrado con éxito en varios casos importantes. ^[1] ${\displaystyle F_{j}(x)}$ ${\displaystyle \pi }$ ${\displaystyle j\in \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle F_{n}}$ ${\displaystyle S}$ ${\displaystyle F_{n}(x)=F_{n}(y)}$ ${\displaystyle y\in S}$ ${\displaystyle x}$ ${\displaystyle F_{n}(x)}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle F_{n}(S)}$ ${\displaystyle \mu }$ ${\displaystyle n}$ ${\displaystyle F_{n}}$

El caso monótono

Existe una clase especial de cadenas de Markov en las que hay opciones particularmente buenas y una herramienta para determinar si . (Aquí denota cardinalidad ). Supongamos que es un conjunto parcialmente ordenado con orden , que tiene un elemento mínimo único y un elemento máximo único ; es decir, todo satisface . Además, supongamos que se puede elegir que se admita en el conjunto de mapas monótonos . Entonces es fácil ver que si y sólo si , ya es monótono. Por lo tanto, comprobar esto resulta bastante fácil. El algoritmo puede continuar eligiendo alguna constante , muestreando los mapas y generando if . Si el algoritmo procede duplicando y repitiendo según sea necesario hasta que se obtenga una salida. (Pero el algoritmo no vuelve a muestrear los mapas que ya fueron muestreados; utiliza los mapas muestreados previamente cuando es necesario). ${\displaystyle \mu }$ ${\displaystyle |F_{n}(S)|=1}$ ${\displaystyle |\cdot |}$ ${\displaystyle S}$ ${\displaystyle \leq }$ ${\displaystyle s_{0}}$ ${\displaystyle s_{1}}$ ${\displaystyle s\in S}$ ${\displaystyle s_{0}\leq s\leq s_{1}}$ ${\displaystyle \mu }$ ${\displaystyle f:S\to S}$ ${\displaystyle |F_{n}(S)|=1}$ ${\displaystyle F_{n}(s_{0})=F_{n}(s_{1})}$ ${\displaystyle F_{n}}$ ${\displaystyle n:=n_{0}}$ ${\displaystyle n_{0}}$ ${\displaystyle f_{-1},\dots ,f_{-n}}$ ${\displaystyle F_{n}(s_{0})}$ ${\displaystyle F_{n}(s_{0})=F_{n}(s_{1})}$ ${\displaystyle F_{n}(s_{0})\neq F_{n}(s_{1})}$ ${\displaystyle n}$ ${\displaystyle f_{-j}}$

Referencias

1. "Sitio web para muestreo perfectamente aleatorio con cadenas de Markov".

• Propp, James Gary; Wilson, David Bruce (1996), Actas de la Séptima Conferencia Internacional sobre Estructuras y Algoritmos Aleatorios (Atlanta, GA, 1995) , págs. 223–252, MR  1611693
• Propp, James; Wilson, David (1998), "Acoplamiento del pasado: una guía del usuario", Microencuestas de probabilidad discreta (Princeton, Nueva Jersey, 1997) , DIMACS Ser. Matemáticas discretas. Teoría. Computadora. Ciencia, vol. 41, Providence, RI: Sociedad Matemática Estadounidense , págs. 181–192, doi :10.1090/dimacs/041/09, ISBN 9780821808276, SEÑOR  1630414, S2CID  2781385