Цепь Маркова

Материал из MachineLearning.

Версия от 13:37, 30 июня 2026; Andrei Blinov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Статья написана с использованием LLM GPT-5.5 Thinking и проверена участником Andrei Blinov 16:37, 30 июня 2026 (MSD)


Цепь Маркова или марковская цепь — случайный процесс, для которого условное распределение будущего состояния при известном настоящем не зависит от всей предыстории процесса. Это свойство называется марковским свойством.

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

Содержание

Интуитивное описание

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

Например, если состояние системы — это погода сегодня, то марковская модель может задавать вероятности погоды завтра в зависимости только от сегодняшней погоды, не учитывая погоду во все предыдущие дни. Такое предположение часто является упрощением, но оно позволяет строить простые и интерпретируемые модели последовательных данных.

Определение

Пусть S — конечное или счётное пространство состояний, а X_0, X_1, X_2, \ldots — последовательность случайных величин со значениями в S. Процесс называется цепью Маркова с дискретным временем, если для любых состояний выполняется равенство:

P(X_{n+1}=j | X_n=i, X_{n-1}=i_{n-1}, \ldots, X_0=i_0)=P(X_{n+1}=j | X_n=i).

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

Если вероятности переходов не зависят от момента времени n, цепь называется однородной по времени. В этом случае вероятность перехода из состояния i в состояние j обозначается так:

p_{ij}=P(X_{n+1}=j | X_n=i).

Далее рассматриваются главным образом однородные цепи Маркова с дискретным временем.

Вероятности переходов

Для каждого состояния i задаётся набор вероятностей перехода в возможные следующие состояния. Число p_{ij} показывает, с какой вероятностью цепь перейдёт из состояния i в состояние j за один шаг.

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

Для любого состояния i вероятности переходов должны удовлетворять двум условиям:

p_{ij}\geq 0,\quad \sum_j p_{ij}=1.

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

Например, если из состояния i возможны переходы в состояния 1,\ldots,m, то числа p_{i1},\ldots,p_{im} задают распределение следующего состояния при условии, что текущее состояние равно i.

Многошаговые переходы

Кроме вероятностей перехода за один шаг, часто рассматривают вероятность попасть из состояния i в состояние j за n шагов. Такую вероятность обозначают

p_{ij}^{(n)}=P(X_n=j | X_0=i).

Для многошаговых переходов выполняется уравнение Чепмена — Колмогорова:

p_{ij}^{(r+s)}=\sum_k p_{ik}^{(r)}p_{kj}^{(s)}.

Это равенство означает, что переход из i в j за r+s шагов можно разбить по промежуточному состоянию k: сначала цепь попадает из i в k за r шагов, а затем из k в j за s шагов.

Графовая интерпретация

Цепь Маркова можно представить как ориентированный взвешенный граф. Вершины графа соответствуют состояниям, а дуга i\to j проводится, если вероятность перехода из i в j положительна. Вес дуги равен вероятности перехода.

Графовая интерпретация удобна при анализе достижимости состояний, случайных блужданий на графах и процессов распространения вероятности по сети.

Классификация состояний

Состояние j называется достижимым из состояния i, если существует такое число шагов n, что вероятность попасть из i в j за n шагов положительна:

p_{ij}^{(n)}>0.

Два состояния i и j называются сообщающимися, если каждое из них достижимо из другого. Цепь называется неприводимой, если все её состояния сообщаются друг с другом.

Состояние i называется поглощающим, если вероятность остаться в нём равна единице:

p_{ii}=1.

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

Периодом состояния i называется наибольший общий делитель всех таких чисел n\geq 1, для которых возможен возврат из состояния i в состояние i за n шагов с положительной вероятностью, то есть для которых выполняется условие

p_{ii}^{(n)}>0.

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

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

Стационарное распределение

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

\pi_j=\sum_i \pi_i p_{ij}.

Также должны выполняться условия нормировки:

\sum_i\pi_i=1,\quad \pi_i\geq 0.

Если начальное состояние имеет стационарное распределение, то распределение состояния в любой последующий момент времени остаётся тем же самым. Поэтому стационарное распределение часто интерпретируют как равновесное распределение цепи.

Для конечной неприводимой цепи стационарное распределение существует и единственно. Если конечная цепь неприводима и апериодична, то при большом числе шагов распределение состояния перестаёт зависеть от начального состояния и сходится к стационарному распределению:

\lim_{n\to\infty}p_{ij}^{(n)}=\pi_j.

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

Цепь Маркова называется обратимой относительно распределения \pi, если выполняется условие детального баланса:

\pi_i p_{ij}=\pi_j p_{ji}.

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

Пример

Рассмотрим цепь Маркова с двумя состояниями:

  • 0 — дождливый день;
  • 1 — солнечный день.

Пусть вероятности переходов заданы следующим образом:

  • если сегодня дождливо, то завтра дождливо с вероятностью p_{00}=0.7, а солнечно с вероятностью p_{01}=0.3;
  • если сегодня солнечно, то завтра дождливо с вероятностью p_{10}=0.2, а солнечно с вероятностью p_{11}=0.8.

Стационарное распределение \pi для этой цепи задаётся двумя числами: \pi_0 и \pi_1. Они удовлетворяют условиям

\pi_0+\pi_1=1,
\pi_0=0.7\pi_0+0.2\pi_1,
\pi_1=0.3\pi_0+0.8\pi_1.

Решение этой системы:

\pi_0=0.4,\quad \pi_1=0.6.

Следовательно, в долгосрочном режиме доля дождливых дней равна 40%, а доля солнечных дней — 60%. Это утверждение относится к среднему поведению цепи на длинном горизонте, а не к конкретной короткой последовательности дней.

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

Для конечной цепи Маркова стационарное распределение можно находить несколькими способами.

Решение системы линейных уравнений

Можно записать уравнения стационарности

\pi_j=\sum_i\pi_i p_{ij}

для всех состояний j и добавить условие нормировки

\sum_i\pi_i=1.

Полученная система линейных уравнений определяет стационарное распределение. Этот способ удобен для небольшого числа состояний.

Последовательное обновление распределения

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

Оценивание по траектории

Если можно сгенерировать длинную траекторию цепи, стационарную вероятность состояния i можно оценить как долю времени, проведённого в этом состоянии:

\hat\pi_i={1\over T}\sum_{t=1}^{T}I(X_t=i).

Такой подход связан с эргодическими теоремами и лежит в основе многих методов семплирования.

Связь с машинным обучением

В машинном обучении цепи Маркова обычно появляются не как самостоятельная модель данных, а как математическая основа более специальных методов.

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

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

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

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

Ограничения марковского предположения

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

  • состояние наблюдается не полностью;
  • важны дальние зависимости;
  • переходы зависят от внешних факторов;
  • динамика меняется со временем;
  • пространство состояний слишком велико для явного задания переходных вероятностей.

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

Типичные ошибки

  • Путать марковское свойство и независимость. В цепи Маркова соседние состояния обычно зависимы; независимость касается условной независимости будущего от прошлого при известном настоящем.
  • Считать, что стационарное распределение всегда единственно. Для конечной цепи единственность обычно требует неприводимости.
  • Путать стационарность и сходимость. Стационарное распределение может существовать, но распределение состояния может не сходиться к нему из-за периодичности.
  • Игнорировать период разогрева в MCMC. Начальная часть траектории может плохо представлять целевое распределение.
  • Использовать слишком бедное состояние. Если текущее состояние не содержит важной информации о прошлом, марковское предположение может давать плохую модель.

См. также

Литература

  • Norris J. R. Markov Chains. Cambridge University Press, 1997.
  • Levin D. A., Peres Y., Wilmer E. L. Markov Chains and Mixing Times. American Mathematical Society, 2017.
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A6%D0%B5%D0%BF%D1%8C_%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D0%B0»