Связь из прошлого

Среди цепи Маркова Монте-Карло (MCMC) алгоритмов связь из прошлого является методом выборки из стационарного распределения цепи Маркова . В отличие от многих алгоритмов MCMC, связь из прошлого в принципе дает идеальную выборку из стационарного распределения . Его изобрели Джеймс Пропп и Дэвид Уилсон в 1996 году.

Основная идея

с конечным состоянием. Рассмотрим неприводимую апериодическую цепь Маркова $M$ с государственным пространством $S$ и (уникальное) стационарное распределение $\pi$ ( $\pi$ — вектор вероятности). Предположим, что мы получили распределение вероятностей $\mu$ на наборе карт $f:S\to S$ со свойством, что для каждого фиксированного $s\in S$, его изображение $f(s)$ распределяется в соответствии с вероятностью перехода $M$ из штата $s$. Примером такого распределения вероятностей является то, где $f(s)$ независим ​ от $f(s')$ в любое время $s\neq s'$, но зачастую стоит рассмотреть и другие дистрибутивы. Теперь позвольте $f_{j}$ для $j\in \mathbb {Z}$ быть независимыми выборками из $\mu$.

Предположим, что $x$ выбирается случайным образом в зависимости от $\pi$ и не зависит от последовательности $f_{j}$. (Мы пока не беспокоимся, где это $x$ исходит откуда.) Тогда $f_{-1}(x)$ также распределяется по $\pi$, потому что $\pi$ является $M$-стационарность и наше предположение о законе $f$. Определять

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

Тогда по индукции следует, что $F_{j}(x)$ также распределяется по $\pi$ для каждого $j\in \mathbb {N}$. Однако может случиться так, что для некоторых $n\in \mathbb {N}$ изображение карты $F_{n}$ представляет собой отдельный элемент $S$.Другими словами, $F_{n}(x)=F_{n}(y)$ для каждого $y\in S$. Поэтому нам не нужен доступ к $x$ чтобы вычислить $F_{n}(x)$. Затем алгоритм включает в себя поиск некоторых $n\in \mathbb {N}$ такой, что $F_{n}(S)$ является синглтоном и выводит элемент этого синглтона. Дизайн хорошего дистрибутива $\mu$ для которого задача найти такое $n$ и вычисления $F_{n}$ не является слишком дорогостоящим, не всегда очевиден, но в ряде важных случаев был успешно реализован.

Монотонный случай

Существует особый класс цепей Маркова, в котором имеются особенно удачные варианты выбора.для $\mu$ и инструмент для определения того, $|F_{n}(S)|=1$. (Здесь $|\cdot |$ обозначает мощность .) Предположим, что $S$ представляет собой частично упорядоченное множество с порядком $\leq$, который имеет уникальный минимальный элемент $s_{0}$ и единственный максимальный элемент $s_{1}$; то есть каждый $s\in S$ удовлетворяет $s_{0}\leq s\leq s_{1}$. Также предположим, что $\mu$ может быть выбран для поддержки на наборе монотонных карт $f:S\to S$. Тогда это легко увидеть $|F_{n}(S)|=1$ тогда и только тогда, когда $F_{n}(s_{0})=F_{n}(s_{1})$, с $F_{n}$ является монотонным. Таким образом, проверить это становится довольно легко. Алгоритм может продолжить работу, выбрав $n:=n_{0}$ для некоторой константы $n_{0}$, выборка карт $f_{-1},\dots ,f_{-n}$и вывод $F_{n}(s_{0})$ если $F_{n}(s_{0})=F_{n}(s_{1})$. Если $F_{n}(s_{0})\neq F_{n}(s_{1})$ алгоритм продолжается путем удвоения $n$ и повторять по мере необходимости до тех пор, пока не будет получен результат. (Но алгоритм не выполняет повторную выборку карт $f_{-j}$ которые уже были отобраны; при необходимости он использует ранее выбранные карты.)

Ссылки

• Пропп, Джеймс Гэри; Уилсон, Дэвид Брюс (1996), Труды Седьмой Международной конференции по случайным структурам и алгоритмам (Атланта, Джорджия, 1995) , стр. 223–252, MR   1611693
• Пропп, Джеймс; Уилсон, Дэвид (1998), «Связь из прошлого: руководство пользователя», Микрообследования по дискретной вероятности (Принстон, Нью-Джерси, 1997) , DIMACS Ser. Дискретная математика. Теория. Вычислить. наук., вып. 41, Провиденс, Род-Айленд: Американское математическое общество , стр. 181–192, doi : 10.1090/dimacs/041/09 , ISBN.  9780821808276 , МР   1630414 , S2CID   2781385