Acoplamiento del pasado

Entre los algoritmos de Monte Carlo de cadena de Markov (MCMC) , el acoplamiento del pasado es un método de muestreo de 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 estado y distribución estacionaria (única) ( es un vector de probabilidad). Supongamos que obtenemos 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 desde el estado . Un ejemplo de tal distribución de probabilidad es aquel donde es independiente de siempre , pero a menudo vale la pena considerar otras distribuciones. Ahora vamos a muestras de ser independiente 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 de acuerdo con y es independiente de la secuencia . (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 . Ahora aquí está el punto principal. Puede suceder que para algunos la imagen del mapa sea ​​un solo elemento de . En otras palabras, para cada uno . 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 calcularla no es 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 .) Suponga 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, suponga que se puede elegir para ser compatible con el conjunto de mapas monótonos . Entonces es fácil ver que si y solo si , ya que es monótono. Por lo tanto, verificar esto se vuelve bastante fácil. El algoritmo puede proceder eligiendo alguna constante${\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}}$, muestreando los mapas y generando si . 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 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. http://www.dbwilson.com/exact/

• 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", Microsurveys en probabilidad discreta (Princeton, NJ, 1997) , DIMACS Ser. Matemáticas discretas. Theoret. Computación. Sci., 41 , Providence, RI: American Mathematical Society , págs. 181-192, doi : 10.1090 / dimacs / 041/09 , ISBN 9780821808276, MR  1630414 , S2CID  2781385