Линейная алгебра · Цепь Маркова

Цепь Маркова

Цепь Маркова случайно переходит между состояниями. Вероятности следующего состояния зависят только от текущего. Если P — матрица переходов, завтрашнее распределение равно сегодняшнему, умноженному справа на P. При повторении оно часто стремится к стационарному распределению π с πP = π, левому собственному вектору для собственного значения 1.

Цепь Маркова на этой схеме

В цепи Маркова вероятности следующего состояния зависят только от текущего. Здесь возможны солнце, облачность и дождь. Строка ii матрицы переходов PP перечисляет вероятности на завтра, если сегодня состояние ii. Каждая строка — вектор вероятностей. Если сегодня распределение задано строкой pp, завтра это pPpP, а через nn дней — pn=p0Pnp_n = p_0 P^n. Для трёх состояний распределения заполняют треугольник: в вершине одно состояние достоверно, а три вероятности задают веса вершин. Тёмные точки — строки PP, синяя — начало, красная линия соединяет p0,p1,p2,…p_0, p_1, p_2, \dots.

Что происходит за один шаг

За шаг каждая вершина переходит в соответствующую строку: если сегодня солнце достоверно, завтра распределение задаёт первая строка. Любое другое распределение pp — взвешенное среднее вершин. Поэтому pPpP — среднее строк с теми же весами. Весь треугольник переходит в меньший треугольник строк, за два шага — в треугольник строк P2P^2. Если у некоторой степени PP все элементы положительны, вложенные треугольники стягиваются к одной точке, стационарному распределению π\pi.

Почему π — собственный вектор и как быстро к нему приближается pₙ

Неподвижная точка удовлетворяет πP=π\pi P = \pi. Следовательно, π\pi — левый собственный вектор для собственного значения 1 (в столбцах PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). Сумма координат разности p0−πp_0 - \pi равна 0. На этом подпространстве у PP остаются два собственных значения λ2,λ3\lambda_2, \lambda_3. В каждом собственном направлении вектор за шаг умножается на соответствующее значение. Если оба модуля меньше 1, то pnp_n стремится к π\pi, а больший модуль ∣λ2∣|\lambda_2| задаёт темп. Для погоды ∣λ2∣≈0.462|\lambda_2| \approx 0.462. При больших nn после шага остаётся чуть меньше половины расстояния, если начальное отклонение имеет составляющую в направлении λ2\lambda_2. При комплексных значениях путь ещё и поворачивает.

Когда распределение не сходится

В цикле солнце, облачность и дождь сменяют друг друга. Два других собственных значения имеют модуль 1, и pnp_n ходит по кругу, если не начать в π\pi. При двух поглощающих состояниях и солнце, и дождь сохраняются. Собственное значение 1 двукратно, любая смесь солнца и дождя неподвижна. Поэтому pnp_n сходится, но предел зависит от старта. В конечной цепи pnp_n стремится к одному и тому же π\pi при любом старте тогда и только тогда, когда есть ровно один замкнутый класс сообщающихся состояний и он апериодичен. Внутри класса все состояния достижимы друг из друга и выхода наружу нет. Достаточно, например, чтобы у некоторой степени PmP^m все элементы были положительны.

На что обратить внимание

  • Для погодной цепи стационарное распределение даёт вероятности погоды в отдалённый день при любом старте. Сама погода продолжает меняться изо дня в день.
  • При числе состояний больше трёх распределения заполняют многомерный аналог треугольника — симплекс. Рассуждение остаётся тем же.

Управление

  • Перетащите тёмную точку, чтобы изменить строку матрицы, или синюю, чтобы изменить старт. Стрелки сдвигают точку в фокусе на одну сотую.

Связанные темы