Цепь Маркова: стационарное распределение

Стационарное распределение цепи Маркова - это набор вероятностей состояний, который сохраняется после каждого перехода. При этом сама система не обязана останавливаться: переходы между состояниями продолжаются, но общий баланс вероятностей остаётся прежним. Ниже найдём такой баланс для двух состояний, проверим вычисление и выясним, когда он действительно описывает поведение на больших временах. В калькуляторе можно менять вероятности переходов и наблюдать, как распределение приближается к стационарному.
Что означает стационарность
Пусть система находится в одном из состояний и . На каждом шаге она может остаться на месте или перейти в другое состояние. Цепь Маркова задаёт вероятности переходов так, что при известном текущем состоянии предыстория не меняет условную вероятность следующего состояния. Например, состояниями могут быть два режима оборудования, если модель считает вероятности переключения постоянными.
Распределение описывает неопределённость относительно состояния в конкретный момент. Если множество одинаковых независимых систем имеет такое распределение, примерно соответствующие доли находятся в каждом состоянии. Это учебная интерпретация, а не дополнительное условие определения.
Стационарный вектор особенный: если взять его начальным распределением, то и через один шаг, и через любое число шагов распределение будет тем же. Он описывает не неподвижность отдельной траектории, а равновесие вероятностных потоков. Связь наблюдаемых данных и скрытых состояний рассматривается отдельно в статье про скрытую марковскую модель.
Матрица переходов и уравнение баланса
Запишем матрицу, где строка соответствует текущему состоянию, а столбец - следующему:
Первая строка говорит: из система остаётся в с вероятностью и переходит в с вероятностью . Во второй строке вероятность перейти из в равна . Элементы неотрицательны, а каждая строка суммируется в единицу.
Будем считать распределение строкой. Тогда после одного шага , а после шагов . Определение стационарности записывается системой
Это задача на левый собственный вектор матрицы с собственным значением , нормированный до суммы единица. Общий взгляд на положительные матрицы и собственные векторы даёт теорема Перрона–Фробениуса; при этом для произвольной матрицы переходов нужно учитывать её классы состояний и периодичность.
Решение для двух состояний
Обозначим . Из первого столбца матричного равенства получаем , то есть . Второе уравнение баланса здесь зависимо от первого: сумма вероятностей уже сохраняется. Поэтому вместе с балансом используем нормировку .
Из равенства потоков следует . Подстановка даёт и . Проверим обе координаты непосредственно:
В равновесии поток из в равен , а обратный поток равен . Так совпадение входящего и исходящего потока делает доли постоянными, хотя на каждом шаге часть систем меняет состояние.
Как распределение приближается к балансу
Начнём с достоверного состояния : . Последовательное умножение на даёт после первого шага, после второго, после третьего и после четвёртого. Вероятность постепенно снижается к .

Для этой матрицы разность между текущей вероятностью и её пределом уменьшается вдвое за шаг: . Формула относится к выбранному начальному состоянию и конкретной матрице. В другой цепи скорость может быть другой, а приближение - колебательным. Калькулятор показывает это при достаточно больших вероятностях перехода в обе стороны.
Результат зависит от начального распределения на конечном числе шагов. Если вместо достоверного состояния начать с достоверного состояния , вероятность сначала равна нулю, после одного шага становится равной , а затем постепенно растёт к тому же значению . Направления изменения разные, но предел совпадает благодаря свойствам именно этой матрицы. Сравнение двух стартов помогает отличить переходный режим от стационарного.
График калькулятора показывает только первые двадцать шагов. Если переходы между состояниями редки, этого горизонта может не хватить для визуального сближения с пунктиром. Отсутствие полного совпадения на экране не означает отсутствия предела: нужно учитывать скорость сходимости и точность отображения. С другой стороны, несколько близких точек сами по себе ещё не доказывают сходимость для произвольной цепи; её устанавливают по свойствам матрицы.
Общая формула и смысл параметров
Пусть - вероятность перехода из в , а - из в . Тогда
если . Формула получается из баланса и нормировки. Чем больше относительно , тем больше стационарная доля : система чаще возвращается в по сравнению с переходом в обратном направлении. В калькуляторе оба параметра ограничены диапазоном от до , поэтому знаменатель положителен и обе вершины сообщаются.
Для этого диапазона отклонение от стационарной вероятности умножается на за шаг. При множитель отрицателен и значения чередуются вокруг предела; при баланс достигается уже после одного шага. Если , оба состояния поглощающие и стационарным будет любое исходное распределение: формула с нулевым знаменателем неприменима.
Как решать систему для нескольких состояний
Для цепи с большим числом состояний метод остаётся тем же, хотя равенства потоков для каждой пары уже необязательны. Для выбранного состояния нужно сложить вероятности всех способов попасть в него за один шаг: вероятность находиться в исходном состоянии умножается на вероятность соответствующего перехода. Полученная сумма должна совпасть со стационарной вероятностью выбранного состояния. Одного равенства для каждой координаты и нормировки достаточно, чтобы записать задачу целиком.
Например, рассмотрим три состояния и матрицу переходов с первой строкой , второй и третьей . Для первой координаты баланс имеет вид , откуда . Аналогично из третьей координаты , поэтому . Нормировка даёт вектор . Подстановка во второе уравнение и проверка суммы завершают решение.
Практический порядок удобен и при использовании программы. Сначала проверьте неотрицательность элементов и суммы строк исходной матрицы. Затем составьте систему, заменив одно зависимое уравнение условием нормировки, и решите её. После этого умножьте найденный вектор на исходную матрицу и сравните результат с самим вектором. При округлённых данных небольшое расхождение может быть вычислительной погрешностью; если же координата отрицательна или сумма заметно отличается от единицы, ответ необходимо пересмотреть.
В общем случае баланс состояния означает равенство суммарного притока и оттока. Требование попарного равенства потоков между каждой парой состояний сильнее: его называют детальным балансом. Оно удобно для построения некоторых цепей, но не является необходимым условием стационарности. Например, движение по трём состояниям по кругу имеет равномерное стационарное распределение, хотя обратные переходы отсутствуют.
Существование, единственность и сходимость
У любой конечной цепи есть хотя бы одно стационарное распределение. Если конечная цепь неприводима, то есть из любого состояния можно добраться до любого другого за некоторое число шагов с положительной вероятностью, распределение единственно. Для сходимости распределения из любого начального состояния к этому вектору достаточно дополнительно апериодичности. Эти результаты и различие между стационарностью и сходимостью изложены в конспекте MIT о конечных цепях Маркова.
Контрпример показывает, зачем проверять период. При вектор стационарен и единственен, но из распределение чередуется между и и не имеет предела. Напротив, если начать сразу с , распределение останется таким на каждом шаге. Стационарность сама по себе не гарантирует сходимость из произвольного старта.
Для моделирования сложных распределений цепь иногда специально строят так, чтобы нужное распределение было стационарным. Эту идею использует алгоритм Метрополиса–Гастингса; его практические оценки также зависят от того, насколько хорошо цепь исследовала пространство состояний. В методе Монте-Карло Метрополиса баланс переходов служит частью обоснования выборки, а не заменяет проверку сходимости.
Частые ошибки
- Перепутать строки и столбцы. При выбранной здесь записи строки - исходные состояния, поэтому строковый вектор умножается на справа.
- Забыть нормировку. Одного уравнения недостаточно: нужны сумма координат единица и их неотрицательность.
- Считать состояние неподвижным. Стационарность относится к распределению; отдельная траектория может переходить между состояниями.
- Приравнять стационарность к пределу без проверки. Периодическая цепь может иметь единственный стационарный вектор без сходимости из фиксированного состояния.
- Применить формулу при . В этом случае деление на невозможно и стационарных распределений бесконечно много.
FAQ
Всегда ли стационарное распределение единственно? Нет. У конечной неприводимой цепи оно единственно, но при нескольких замкнутых классах могут существовать разные стационарные распределения.
Что делать для трёх и более состояний? Решить систему вместе с , проверить неотрицательность и подставить ответ обратно. Одно из зависимых уравнений удобно заменить нормировкой.
Равна ли вероятность состояния доле времени в нём? Для конечной неприводимой цепи долгосрочная частота посещений состояния вдоль траектории сходится к соответствующей стационарной вероятности. Это утверждение о средних по времени отличается от сходимости распределения на каждом отдельном шаге.
Коротко
Стационарное распределение - нормированный неотрицательный вектор, удовлетворяющий . Для матрицы с переходами вероятности и вероятности оно равно . Единственность и сходимость проверяют отдельно по структуре цепи и её периоду.
Читайте также

Процесс рождения и гибели: модель и примеры
Процесс рождения и гибели простыми словами: интенсивности переходов, уравнения Колмогорова и стационарное распределение на примере очереди с ограничением.

Уравнения Чепмена-Колмогорова: как связаны переходы
Уравнения Чепмена-Колмогорова простыми словами: как из переходов за n и m шагов получить переход за n+m, дискретная и непрерывная формы, связь с матрицей и стационарным распределением.

Дивергенция Кульбака-Лейблера: смысл и расчёт
Дивергенция Кульбака-Лейблера простыми словами: формула и пример расчёта для двух исходов, асимметрия, нулевые вероятности и связь с энтропией и обучением моделей.

Геометрическая вероятность: задача о встрече
Как решить задачу о встрече через геометрическую вероятность: квадрат времён прихода, область встречи, расчёт для ожидания 15 минут и варианты условий.

Неравенство Маркова и Чебышёва: сравнение оценок
Неравенства Маркова и Чебышёва оценивают вероятность по среднему и дисперсии. Сравним границы одного события, проверим условия и разберём примеры равенства.

Парадокс дней рождения: вероятность совпадения
Парадокс дней рождения объясняет, почему уже в группе из 23 человек вероятность общей даты превышает 50 %. Выведем формулу, сравним случаи и проверим ограничения модели.