Стационарные распределения и эргодичность

Стационарное распределение — это вероятностное распределение по состояниям, которое цепь Маркова оставляет неизменным, и при мягких условиях цепь забывает свою начальную точку и сходится к этому равновесию, при этом временные средние соответствуют пространственным средним.

Definition

Стационарное распределение цепи Маркова — это вероятностное распределение по состояниям, которое инвариантно относительно одного шага цепи, а цепь является эргодической, когда из любого начального состояния ее распределение сходится к этому стационарному распределению, а ее временные средние сходятся к стационарным ожиданиям.

Scope

Тема охватывает стационарные и инвариантные распределения, их существование и единственность для неприводимых положительно-возвратных цепей, роль апериодичности в сходимости, детальный баланс и обратимость, эргодическую теорему цепей Маркова, приравнивающую долгосрочные временные средние к стационарным ожиданиям, скорость сходимости к равновесию и времена перемешивания, а также использование этих идей в методах Монте-Карло для цепей Маркова.

Core questions

• Когда цепь Маркова обладает единственным стационарным распределением?
• При каких условиях распределение цепи сходится к этому стационарному распределению?
• Что такое детальный баланс и как обратимость упрощает нахождение стационарного распределения?
• Как долгосрочные временные средние соотносятся со средними значениями при стационарном распределении?

Key concepts

• стационарное распределение
• неприводимость и апериодичность
• детальный баланс
• эргодическая теорема
• время перемешивания

Key theories

Существование, единственность и сходимость к стационарности

Неприводимая положительно-возвратная цепь Маркова имеет единственное стационарное распределение, задаваемое обратными значениями средних времен возврата, и если она также апериодична, то распределение состояния сходится к нему из любой начальной точки.

Эргодическая теорема цепей Маркова

Для неприводимой положительно-возвратной цепи долгосрочное среднее значение функции состояния сходится почти наверное к ее математическому ожиданию при стационарном распределении, что является аналогом закона больших чисел для зависимых марковских данных.

Детальный баланс и обратимость

Если распределение удовлетворяет детальному балансу с вероятностями перехода, что означает баланс потока между любыми двумя состояниями в обоих направлениях, то оно является стационарным, а цепь обратима — условие, используемое для разработки сэмплеров Монте-Карло для цепей Маркова.

Clinical relevance

Эти результаты являются теоретической основой методов Монте-Карло для цепей Маркова, где цепь разрабатывается таким образом, чтобы целевое распределение было ее стационарным законом, и ее выборки аппроксимировали это распределение; границы времени перемешивания показывают специалистам, как долго следует проводить такие симуляции, и та же теория управляет равновесными длинами очередей и стационарной надежностью.

History

Теория равновесия цепей Маркова выросла из оригинальных работ Маркова и была приведена к современной форме Дубом, Феллером и другими. Ее прикладное значение резко возросло с появлением алгоритма Метрополиса в 1953 году и обобщения Гастингса в 1970 году, которые превратили сходимость к стационарному распределению в практический метод вычислений.

Key figures

• Andrey Markov
• Nicholas Metropolis
• Wilfred Keith Hastings
• Sean Meyn

Seminal works

• norris1997

Frequently asked questions

Каждая ли цепь Маркова сходится к стационарному распределению?

Нет; сходимость требует таких условий, как неприводимость, положительная возвратность и апериодичность. Периодическая цепь может циклически повторяться, не устанавливаясь, а транзиентная или нулевая возвратная цепь может вообще не иметь стационарного распределения.

Почему обратимость полезна на практике?

Обратимость через детальный баланс дает простое уравнение, которому должно удовлетворять потенциальное стационарное распределение, что как облегчает проверку стационарного распределения, так и обеспечивает принцип проектирования, лежащий в основе алгоритмов Метрополиса-Гастингса и многих других алгоритмов Монте-Карло для цепей Маркова.