Время смешивания цепи Маркова

В теории вероятностей цепи время смешивания Маркова — это время, пока цепь Маркова не станет «близкой» к своему установившемуся распределению .

Точнее, фундаментальный результат о цепях Маркова состоит в том, что неприводимая апериодическая цепь с конечным состоянием имеет единственное стационарное распределение π и, независимо от начального состояния, распределение времени -t цепи сходится к π, когда t стремится к бесконечности. Время смешивания относится к любому из нескольких вариантов формализации идеи: насколько большим должно быть t , чтобы распределение времени -t стало примерно π ? Один вариант, время смешивания общего расстояния вариации , определяется как наименьшее t, при котором общее расстояние вариации вероятностных мер невелико:

t_{\mathrm {mix} }(\epsilon )=\min\{t\geq 0:\max _{x\in S}{\Big [}\max _{A\subseteq S}{\big |}\Pr(X_{t}\in A\mid X_{0}=x)-\pi (A){\big |}{\Big ]}\leq \epsilon \}

.

Выбор другого $\epsilon$ , пока $\epsilon <1/2$ , может изменять время перемешивания только до постоянного коэффициента (в зависимости от $\epsilon$ ) и поэтому часто исправляют $\epsilon =1/4$ и просто пишет $t_{\mathrm {mix} }$ .

Именно в этом смысле Дэйв Байер и Перси Диаконис ( 1992 ) доказали, что количество тасовок, необходимых для смешивания обычной колоды из 52 карт, равно 7. Математическая теория фокусируется на том, как время смешивания меняется в зависимости от размера лежащей в основе структуры. цепь. Для $n$ -колоду карт, количество необходимых перетасовок увеличивается по мере $1.5\log _{2}n$ . Наиболее развитая теория касается рандомизированных алгоритмов для #P-полных алгоритмических задач подсчета, таких как количество раскрасок графа заданного числа. $n$ граф вершин. На такие проблемы для достаточно большого числа цветов можно ответить, используя метод Монте-Карло для цепей Маркова и показав, что время смешивания растет только как $n\log(n)$ ( Джеррам 1995 ). Этот пример и пример перетасовки обладают свойством быстрого перемешивания : время перемешивания увеличивается полиномиально быстро в $\log$ (количество состояний цепи). Инструменты доказательства быстрого смешивания включают аргументы, основанные на проводимости и методе связи . При более широком использовании метода Монте-Карло цепи Маркова строгое обоснование результатов моделирования потребует теоретического ограничения времени смешивания, и многие интересные практические случаи сопротивляются такому теоретическому анализу.

См. также [ править ]

Смешивание (математика) для формального определения смешивания

Ссылки [ править ]

Олдос, Дэвид; Филл, Джим, Обратимые цепи Маркова и случайные блуждания по графикам , заархивировано из оригинала 21 сентября 2004 г.
Байер, Дэйв ; Диаконис, Перси (1992), «Следуя за ласточкиным хвостом к его логову» (PDF) , The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR 2959752 , MR 1161056 .
Джеррум, Марк (1995), «Очень простой алгоритм оценки количества $k$ -раскрасок графа низкой степени», Random Structures & Algorithms , 7 (2): 157–165, doi : 10.1002/rsa.3240070205 , МР 1369061 .
Левин, Дэвид А.; Перес, Юваль ; Уилмер, Элизабет Л. (2009), Марковские цепи и времена смешивания , Провиденс, Род-Айленд: Американское математическое общество, ISBN 978-0-8218-4739-8 , МР 2466937 .
Синклер, Алистер (1993), Алгоритмы случайной генерации и подсчета: подход с использованием цепей Маркова , Прогресс в теоретической информатике, Birkhäuser Boston, Inc., Бостон, Массачусетс, номер документа : 10.1007/978-1-4612-0323-0 , ISBN 0-8176-3658-7 , МР 1201590 .