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

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

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

${\displaystyle 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 \}}$.

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

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

Смотрите также

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

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

• Олдос, Дэвид; Филл, Джим, Обратимые цепи Маркова и случайные блуждания по графикам, заархивировано из оригинала 21 сентября 2004 г..
• Байер, Дэйв ; Диаконис, Перси (1992), «Следуя за ласточкиным хвостом к его логову» (PDF) , Анналы прикладной теории вероятностей , 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.