Koppling från det förflutna

Bland Markov-kedjans Monte Carlo (MCMC) algoritmer är koppling från det förflutna en metod för provtagning från den stationära distributionen av en Markov-kedja . I motsats till många MCMC-algoritmer ger koppling från det förflutna i princip ett perfekt urval från den stationära fördelningen . Den uppfanns av James Propp och David Wilson 1996.

Grundidén

Betrakta en ändlig tillstånd irreducerbar aperiodisk Markov-kedja $M$ med tillståndsutrymme $S$ och (unik) stationär fördelning $\pi$ ( $\pi$ är en sannolikhetsvektor). Antag att vi kommer fram till en sannolikhetsfördelning $\mu$ på kartuppsättningen $f:S\to S$ med egenskapen att för varje fast $s \i S$ , dess bild $f(s)$ fördelas enligt övergångssannolikheten för $M$ från tillstånd $s$ . Ett exempel på en sådan sannolikhetsfördelning är den där $f(s)$ är oberoende av $f(s')$ närhelst $s\ neq s'$ , men det är ofta värt att överväga andra distributioner. Låt nu $f_{j}$ för $j\in \mathbb {Z}$ vara oberoende sampel från $\mu$ .

Antag att $x$ väljs slumpmässigt enligt $\pi$ och är oberoende av sekvensen $f_{j}$ . (Vi oroar oss inte för nu var denna $x$ kommer ifrån.) Sedan är $f_{-1}(x)$ också fördelat enligt $\pi$ , eftersom $\pi$ är $M$ -stationär och vårt antagande om lagen om $f$ . Definiera

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

Sedan följer med induktion att $F_{j}(x)$ också fördelas enligt $\pi$ för varje $j\in \mathbb {N}$ . Det kan dock hända att för vissa ${\displaystyle n\in \mathbb {N} } är$ bilden av kartan $F_{n}$ ett enda element av $S$ . Med andra ord, $F_{n}(x)=F_{n}(y)$ för varje $y\in S$ . Därför behöver vi inte ha tillgång till $x$ för att beräkna $F_{n}(x)$ . Algoritmen innebär sedan att hitta några $n\in \mathbb {N}$ så att $F_{n}(S)$ är en singelton , och mata ut elementet för den singeltonen . Utformningen av en bra distribution $\mu$ för vilken uppgiften att hitta en sådan $n$ och beräkna $F_{n}$ inte är alltför kostsam är inte alltid självklar, men har har genomförts framgångsrikt i flera viktiga fall.

Det monotona fallet

Det finns en speciell klass av Markov-kedjor där det finns särskilt bra val för $\mu$ och ett verktyg för att avgöra om $|F_{n}(S)|=1$ . (Här betecknar $|\cdot |$ kardinalitet .) Antag att $S$ är en delvis ordnad uppsättning med ordningen ${\displaystyle \leq } ,$ som har ett unikt minimalt element $s_{0}$ och ett unikt maximalt element $s_{1}$ ; det vill säga varje $s\in S$ uppfyller $s_{0}\leq s\leq s_{1}$ . Anta också att $\mu$ kan väljas för att stödjas på uppsättningen monotona kartor $f:S\to S$ . Då är det lätt att se att $|F_{n}(S)|=1$ om och endast om $F_{n}(s_{0})=F_{n }(s_{1})$ , eftersom $F_{n}$ är monoton. Därför blir det ganska enkelt att kontrollera detta. Algoritmen kan fortsätta genom att välja $n:=n_{0}$ för någon konstant $n_{0}$ , sampla kartorna $f_ {-1},\dots ,f_{-n}$ och utmatning av $F_{n}(s_{0})$ om ${ \displaystyle F_{n}(s_{0})=F_{n}(s_{1})}$ . Om $F_{n}(s_{0})\neq F_{n}(s_{1})$ fortsätter algoritmen genom att dubbla $n$ och upprepa vid behov tills en utdata erhålls. (Men algoritmen samplar inte om kartorna $f_{-j}$ som redan samplades; den använder de tidigare samplade kartorna när det behövs.)

•   Propp, James Gary; Wilson, David Bruce (1996), Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995) , s. 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. Diskret matematik. Teoret. Comput. Sci., vol. 41, Providence, RI: American Mathematical Society , s. 181–192, doi : 10.1090/dimacs/041/09 , ISBN 9780821808276 , MR 1630414 , S2CID 2781385