Acoplamiento del pasado

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

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

Supongamos que${\displaystyle x}$se elige aleatoriamente según${\displaystyle \pi }$y es independiente de la secuencia${\displaystyle f_{j}}$. (Por ahora no nos preocupa dónde está esto${\displaystyle x}$(viene de.) Entonces${\displaystyle f_{-1}(x)}$También se distribuye según${\displaystyle \pi }$, porque${\displaystyle \pi }$es${\displaystyle M}$-estacionario y nuestra suposición sobre la ley de${\displaystyle f}$. Definir

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

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

Existe una clase especial de cadenas de Markov en la que hay opciones particularmente buenas para${\displaystyle \mu }$y una herramienta para determinar si${\displaystyle |F_{n}(S)|=1}$. (Aquí${\displaystyle |\cdot |}$denota cardinalidad .) Supongamos que${\displaystyle S}$es un conjunto parcialmente ordenado con orden${\displaystyle \leq }$, que posee un elemento mínimo único${\displaystyle s_{0}}$y un elemento máximo único${\displaystyle s_{1}}$; es decir, cada${\displaystyle s\in S}$Satisface${\displaystyle s_{0}\leq s\leq s_{1}}$. Además, supongamos que${\displaystyle \mu }$puede elegirse para ser soportado en el conjunto de mapas monocromáticos${\displaystyle f:S\to S}$Entonces es fácil ver que${\displaystyle |F_{n}(S)|=1}$si y solo si${\displaystyle F_{n}(s_{0})=F_{n}(s_{1})}$, desde${\displaystyle F_{n}}$es monótono. Por lo tanto, comprobar esto resulta bastante fácil. El algoritmo puede proceder eligiendo${\displaystyle n:=n_{0}}$por alguna constante${\displaystyle n_{0}}$muestreando los mapas${\displaystyle f_{-1},\dots ,f_{-n}}$y generando${\displaystyle F_{n}(s_{0})}$si${\displaystyle F_{n}(s_{0})=F_{n}(s_{1})}$. Si${\displaystyle F_{n}(s_{0})\neq F_{n}(s_{1})}$El algoritmo procede duplicando${\displaystyle n}$y repitiendo según sea necesario hasta obtener una salida. (Pero el algoritmo no vuelve a muestrear los mapas.${\displaystyle f_{-j}}$ which were already sampled; it uses the previously sampled maps when needed.)

• Propp, James Gary; Wilson, David Bruce (1996), Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), pp. 223–252, MR 1611693
• Propp, James; Wilson, David (1998), "Coupling from the past: a user's guide", Microsurveys in discrete probability (Princeton, NJ, 1997), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 41, Providence, R.I.: American Mathematical Society, pp. 181–192, doi:10.1090/dimacs/041/09, ISBN 9780821808276, MR 1630414, S2CID 2781385