Инвариантный закон и асимптотика

Инвариантный закон и асимптотика

Мы стремимся понять асимптотическое поведение однородной цепи Маркова. То есть предел переходных вероятностей Q^нет(i,j) когда n становится очень большим (закон инварианта).

Идея

Мы стремимся ответить на следующий вопрос: «Какова вероятность того, что после n
не здесь цепь маркова находиться в заданном состоянии? ". Возьмем следующую матрицу перехода P:

Предположим, что ни одна из машин не простаивает в первый день. Тогда у нас есть исходный вектор (1, 0), для вычисления следующего распределения мы умножаем исходный вектор на P и т. д. Что дает полученные результаты следующий :

Это означает, что после 10 итераций, если мы считаем, что мы начинаем с состояния 0, мы имеем 99% в состоянии 0 и 1% в состоянии 1. Это также можно интерпретировать следующим образом: на начальной популяции, учитывая начальное распределение по вектору (1,0), то 99% популяции будут в состоянии 0, а 1% в состоянии 1.

Мы замечаем, что четвертая и десятая итерации имеют близкие результаты (здесь идентичные 4 значащим цифрам). Тогда мы говорим о законе сходимости, и этот закон не зависит от распределения в начале координат.

Периодичность

Возьмем пример следующей матрицы P={0, 1; 1, 0}. Заметим, что P²=Id, что влечет за собой следующее соотношение: ∀n∈Ν, P^2н+1=П.

Такая цепь не сходится, она называется 2-периодической или периода 2.

Перед вычислением закона инварианта цепи Маркова необходимо проверить, что последняя неприводима и апериодична (называется также эргодической).

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

Инвариантный закон

Говорят, что вероятностная мера π инвариантна или стационарна, если для переходной матрицы P мы имеем πP=π. Обратите внимание, что поскольку π является мерой, сумма этих членов равна 1.

Пусть (Xn), определяющая однородную цепь Маркова с P, является неприводимой и апериодической переходной матрицей, имеющей инвариантную меру π. Так :

• P(Xn = x) → π(x), когда n → ∞ для всех x
• п^нет(x, y) → π(y), когда n → ∞ для всех x, y

Скорость сходимости к стационарному закону порядка |ζ|^нет где ζ — собственное значение P, отличное от 1 и имеющее наибольший модуль (строго меньше 1).

Если цепь эргодическая (неприводимая и апериодическая), то все состояния достижимы из любого другого состояния. Такая цепь имеет закон инвариантности.

Точный расчет измерения

Возьмем определение µP=µ, зная, что µ является стохастическим (и да, я изменил название начального распределения!). Это дает следующую линейную систему:

Мера µ на E инвариантна (для P), если µ = µP, т. е.: для всех y ∈ E

Мы говорим об инвариантном распределении, если, кроме того, µ является вероятностью (µ(E) = 1). Мы также говорим закон/инвариант/стационарная вероятность.

Учитывая соотношение µ_п+1 = мк_нетP, мы сразу замечаем, что если µ — инвариантное распределение и X₀ ∼ µ, то X_нет ∼ µ для всех n. Заметим также, что µ не зависит от начального вектора распределения.

Возьмем, к примеру, цепь Маркова с тремя состояниями, матрица переходов которой имеет следующий вид:

Мы сразу замечаем, что матрица образует неприводимую и апериодическую цепочку, так как все состояния сообщаются и что p_II >0. Мы пытаемся решить систему µP=µ с решением µ*= (p, q, r), таким что p+q+r=1 и 0 <p,q,r <1 ce qui donne les équations suivantes :

В качестве решения находим вектор µ*=(2/53, 10/53, 41/53).

Точное вычисление меры (неэргодичный случай)

Рассмотрим следующую цепь Маркова

Мы находим, что состояние 1 образует переходный класс, состояние 2 образует поглощающий класс, а состояния 3, 4 образуют рекуррентный класс. Проведем анализ асимптотики, не принимая во внимание ее неэрготический характер (нет гарантии сходимости).

Решим следующую систему:

Система не допускает единственного решения. Пусть α находится между 0 и 1, тогда мы находим решение, допуская, что α является решением π2:

Мы замечаем в классе {3,4}, что вероятности равны на частоте 2k, мы делаем вывод, что класс является периодическим на периоде 2 (который мы могли бы вычислить по степени матрицы). Класс {2} поглощающий, периода нет. Класс {1} является переходным, поэтому через время k популяции больше нет.

В случае непериодической цепи из асимптотического поведения можно вывести классы состояний, а также периодичность классов и цепи.