WikiDer > Муфта из прошлого

Среди Цепь Маркова Монте-Карло (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} (х)}$ также распределяется по ${ displaystyle pi}$, потому что ${ displaystyle pi}$ является ${ displaystyle M}$-стационарность и наше предположение о законе ${ displaystyle f}$. Определять

${ displaystyle F_ {j}: = f _ {- 1} circ f _ {- 2} circ cdots circ f _ {- j}.}$

Тогда по индукции следует, что ${ Displaystyle F_ {j} (х)}$ также распределяется по ${ displaystyle pi}$ для каждого ${ displaystyle j in mathbb {N}}$. А теперь самое главное. Может случиться так, что для некоторых ${ Displaystyle п в mathbb {N}}$ изображение карты ${ displaystyle F_ {n}}$ является единственным элементом ${ displaystyle S}$.Другими словами, ${ Displaystyle F_ {п} (х) = F_ {п} (у)}$ для каждого ${ displaystyle y in S}$. Следовательно, нам не нужно иметь доступ к ${ displaystyle x}$ чтобы вычислить ${ Displaystyle F_ {п} (х)}$. Затем алгоритм включает поиск некоторых ${ Displaystyle п в mathbb {N}}$ такой, что ${ Displaystyle F_ {п} (S)}$ это одиночкаи выводит элемент этого синглтона. Дизайн хорошей раздачи ${ displaystyle mu}$ для чего стоит задача найти такой ${ displaystyle n}$ и вычисления ${ displaystyle F_ {n}}$ не слишком затратно, не всегда очевидно, но в нескольких важных случаях удалось успешно.^[1]

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

Существует особый класс цепей Маркова, в котором есть особенно хорошие варианты для ${ displaystyle mu}$ и инструмент для определения того, ${ displaystyle | F_ {n} (S) | = 1}$. (Здесь ${ displaystyle | cdot |}$ обозначает мощность.) Предположим, что ${ displaystyle S}$ это частично заказанный набор с заказом ${ displaystyle leq}$, имеющий уникальный минимальный элемент ${ displaystyle s_ {0}}$ и единственный максимальный элемент ${ displaystyle s_ {1}}$; то есть каждый ${ 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})}$ алгоритм работает путем удвоения ${ displaystyle n}$ и повторение по мере необходимости, пока не будет получен результат. (Но алгоритм не выполняет повторную выборку карт ${ displaystyle f _ {- j}}$ которые уже были отобраны; при необходимости он использует ранее отобранные карты.)

Рекомендации

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