Sprzęgło z przeszłości

Wśród algorytmów Monte Carlo łańcucha Markowa (MCMC) , sprzężenie z przeszłości jest metodą próbkowania ze stacjonarnego rozkładu łańcucha Markowa . W przeciwieństwie do wielu algorytmów MCMC, sprzężenie z przeszłości daje w zasadzie idealną próbkę z rozkładu stacjonarnego . Został wynaleziony przez Jamesa Proppa i Davida Wilsona w 1996 roku.

Podstawowa idea

Rozważmy nieredukowalny aperiodyczny łańcuch Markowa $wektorem$$z$$skończonym$ przestrzenią $. Załóżmy,$ i (unikatowym) rozkładem stacjonarnym jest prawdopodobieństwa) $s$ wymyślimy rozkład prawdopodobieństwa $map$$w S}$ z , że dla każdego ustalonego $s$$\$$obraz$ jego jest $rozłożony$ zgodnie ze Przykładem takiego rozkładu prawdopodobieństwa jest ten, w którym $')}$ ( s ′ $s$${\ Displaystyle s \ neq s'}$ ilekroć , ale często warto rozważyć inne dystrybucje. Teraz $\$ dla $będzie$ niezależnymi próbkami od $mu$ .

Załóżmy, że $j}}$$wybierany losowo$$jot {\ displaystyle f_$ z i jest niezależny od sekwencji . (Na $jest$ nie martwimy się, skąd to $.$ Następnie również dystrybuowane zgodnie z $}$$displaystyle \$ , ponieważ $-stacjonarne i nasze$$displaystyle$ dotyczące prawa $f}$ \ . Definiować

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

$dla$ wynika, że $Displaystyle j \ w \ mathbb {N} }$ również dystrybuowany zgodnie z $\ Displaystyle \ pi}$ każdego . $}$ może się zdarzyć, że dla niektórych obraz $jest$ pojedynczym elementem $S$ Innymi słowy, dla każdego ${\ Displaystyle F_ {n} (x) = F_ {n} (y)}$${\ Displaystyle y \ w S}$ . Dlatego nie musimy mieć dostępu do , ${\ displaystyle F_ {n} (x)$ obliczyć . $x$ } Algorytm polega następnie $że$ znalezieniu $takiego$ jest singletonem tego . Projekt dobrej dystrybucji, $której$ zadanie znalezienia takiego $.$$ma$ nie zbyt kosztowne, nie zawsze jest oczywiste, ale zakończyło się pomyślnie w kilku ważnych przypadkach.

Sprawa monotonna

Istnieje specjalna klasa łańcuchów Markowa, w której istnieją szczególnie dobre wybory dla ${\ displaystyle \ mu}$ i narzędzie do określania, czy ${\ Displaystyle | F_ {n} (S) | = 1}$ . (Tutaj $Displaystyle |\ cdot |}$$\$ oznacza liczność .) Załóżmy, że $S}$ to częściowo uporządkowany zestaw z porządkiem , który ma unikalny element minimalny . $s_ {0}}$$\ displaystyle$ i unikalny element maksymalny ${\ displaystyle s_ {1}}$ ; to znaczy, że każdy spełnia $\$$Displaystyle s_ {0} \ równoważnik s \ równoważnik$ . Załóżmy również, że można wybrać obsługę zestawu map monotonicznych $S$${\ displaystyle f: S \ do$ . Wtedy łatwo zauważyć, że ${\ Displaystyle | F_ {n} (S) | = 1}$ wtedy i tylko wtedy, gdy ${\ Displaystyle F_ {n} (s_ {0}) = F_ {n } (s_ {1})}$$ponieważ$ jest . W ten sposób sprawdzenie tego staje się raczej łatwe. Algorytm może kontynuować, wybierając ${-1} \ kropki, f_ {- n}}$$pewnej$$f_$ , próbkując mapy $\$ i wyprowadzanie ${\ Displaystyle F_ {n} (s_ {0})}$ jeśli ${ \displaystyle F_{n}(s_{0})=F_{n}(s_{1})}$ . fa ${\ Displaystyle F_ {n} (s_ {0}) \ neq F_ {n} (s_ {1})}$ algorytm postępuje przez podwojenie ${\ displaystyle n$ i powtarzanie w razie potrzeby aż do uzyskania wyjścia. (Ale algorytm nie próbkuje $próbkowane ; w razie$ map, które były już map próbkowanych wcześniej).

•   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), „Sprzęganie z przeszłości: podręcznik użytkownika”, Microsurveys in dyskretnego prawdopodobieństwa (Princeton, NJ, 1997) , DIMACS Ser. Dyskretna matematyka. teoria. Oblicz. Nauka, tom. 41, Providence, RI: American Mathematical Society , s. 181–192, doi : 10.1090/dimacs/041/09 , ISBN 9780821808276 , MR 1630414 , S2CID 2781385