過去との結びつき

マルコフ連鎖モンテカルロ（MCMC）アルゴリズムの中でも、過去からの結合は、マルコフ連鎖の定常分布からサンプリングを行う手法の一つです。多くのMCMCアルゴリズムとは異なり、過去からの結合は原理的に定常分布から完全なサンプルを提供します。この手法は、1996年にジェームズ・プロップとデビッド・ウィルソンによって考案されました。

有限状態の既約非周期マルコフ連鎖を考える${\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 }$。

仮に${\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}.}$

すると帰納法により次のことが導かれる。${\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}}$費用がかかりすぎるわけではないが、必ずしも明白ではないものの、いくつかの重要な事例で成功裏に達成されている。^{[ 1 ]}

マルコフ連鎖には、特に優れた選択肢がある特別なクラスがあります。${\displaystyle \mu }$そして、${\displaystyle |F_{n}(S)|=1}$。 （ここ${\displaystyle |\cdot |}$（濃度を表す。）${\displaystyle S}$順序を持つ部分順序集合${\displaystyle \leq }$独自のミニマルな要素を持つ$s0$そして、独特の最大要素$s1$つまり、すべての${\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})}$アルゴリズムは、2倍にすることで進行します${\displaystyle n}$そして、出力が得られるまで必要に応じて繰り返す。（ただし、このアルゴリズムはマップを再サンプリングしない。）${\displaystyle f_{-j}}$（既にサンプリング済みのマップを使用します。必要に応じて、以前にサンプリングされたマップを使用します。）

• 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)、「過去からの結合：ユーザーガイド」、Microsurveys in discrete probability (Princeton, NJ, 1997)、DIMACS Ser. Discrete Math. Theoret. Comput. Sci.、vol.  41、Providence, RI: American Mathematical Society、pp. 181–192、doi : 10.1090/dimacs/041/09、ISBN  9780821808276MR 1630414、S2CID 2781385​