Марковский процесс

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

Версия от 15:10, 28 июня 2026; Andrei Blinov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM GPT-5.5 Thinking и проверена участником Andrei Blinov 18:09, 28 июня 2026 (MSD)

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

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

Содержание

1 Определение
2 Переходные вероятности
3 Однородные и неоднородные процессы
4 Цепь Маркова
5 Марковские процессы в непрерывном времени
6 Стационарное распределение
7 Классификация состояний
8 Обратимость и детальный баланс
9 Сильное марковское свойство
10 Примеры
11 Марковские процессы в машинном обучении
12 Оценивание параметров
13 Типичные замечания
14 См. также
15 Литература
16 Ссылки

Определение

Пусть ${X_t}_{t\in T}$ — стохастический процесс со значениями в пространстве состояний $E$ . Процесс называется марковским, если для любых моментов времени $s<t$ условное распределение $X_t$ при известной истории процесса до момента $s$ зависит только от текущего состояния $X_s$ .

В дискретном времени это свойство записывается как

$\mathbb{P}(X_{n+1}=x_{n+1}\mid X_n=x_n,\ldots,X_0=x_0)=\mathbb{P}(X_{n+1}=x_{n+1}\mid X_n=x_n).$

Для произвольного измеримого множества $B\subseteq E$ :

$\mathbb{P}(X_{n+1}\in B\mid X_0,\ldots,X_n)=\mathbb{P}(X_{n+1}\in B\mid X_n).$

Марковское свойство не означает независимости случайных величин $X_0,X_1,\ldots$ . Оно означает условную независимость будущего от прошлого при известном настоящем.

Переходные вероятности

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

$P(x,B)=\mathbb{P}(X_{n+1}\in B\mid X_n=x).$

Если пространство состояний конечно, $E={1,\ldots,m}$ , то переходы задаются матрицей переходных вероятностей

$P_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i),\quad i,j\in E.$

Элементы матрицы удовлетворяют условиям

$P_{ij}\geq 0,\qquad \sum_j P_{ij}=1.$

Если начальное распределение задано строковым вектором $\mu_0$ , то распределение через $n$ шагов равно

$\mu_n=\mu_0P^n.$

Элемент $(P^n)_{ij}$ равен вероятности перейти из состояния $i$ в состояние $j$ за $n$ шагов.

Однородные и неоднородные процессы

Марковский процесс называется однородным по времени, если вероятности перехода зависят только от длины временного интервала, но не от начального момента времени:

$\mathbb{P}(X_{s+t}\in B\mid X_s=x)=P_t(x,B).$

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

$P(s,x;t,B)=\mathbb{P}(X_t\in B\mid X_s=x).$

Для однородного марковского процесса переходные функции удовлетворяют уравнению Чепмена — Колмогорова

$P_{t+u}(x,B)=\int_E P_t(x,dy)P_u(y,B).$

В конечном дискретном случае это уравнение сводится к умножению матриц:

$P^{n+m}=P^nP^m.$

Цепь Маркова

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

Пример процесса с двумя состояниями $0$ и $1$ :

$P=\begin{pmatrix}1-a & a\ b & 1-b\end{pmatrix},\qquad 0\leq a,b\leq 1.$

Такая модель может описывать переходы между двумя режимами, например «исправен» и «неисправен» или «активен» и «неактивен».

Марковские процессы в непрерывном времени

Если множество моментов времени непрерывно, например $T=[0,\infty)$ , говорят о марковском процессе в непрерывном времени.

Для конечного пространства состояний такой процесс часто задаётся инфинитезимальным генератором $Q=(q_{ij})$ , где

$q_{ij}\geq 0,\quad i\neq j,\qquad q_{ii}=-\sum_{j\neq i}q_{ij}.$

Число $q_{ij}$ интерпретируется как интенсивность перехода из состояния $i$ в состояние $j$ . Матрица переходных вероятностей за время $t$ выражается через матричную экспоненту:

$P_t=e^{tQ}.$

Если $\mu_t$ — распределение процесса в момент $t$ , то для конечной непрерывновременной цепи выполняется прямое уравнение Колмогорова

$\frac{d\mu_t}{dt}=\mu_t Q.$

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

Стационарное распределение — это распределение $\pi$ , которое не меняется при применении переходного оператора. Для дискретной цепи Маркова оно удовлетворяет уравнению

$\pi=\pi P.$

В координатах:

$\pi_j=\sum_i \pi_iP_{ij},\qquad \sum_j\pi_j=1,\qquad \pi_j\geq 0.$

Если цепь запущена из стационарного распределения, то распределение $X_n$ остаётся равным $\pi$ для всех $n$ .

Для непрерывновременной конечной цепи стационарное распределение удовлетворяет

$\pi Q=0.$

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

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

Достижимость и неприводимость

Состояние $j$ называется достижимым из состояния $i$ , если существует $n\geq 0$ , такое что

$(P^n)_{ij}>0.$

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

Рекуррентность и транзиентность

Состояние называется рекуррентным, если процесс, стартовав из него, возвращается в него с вероятностью $1$ . Состояние называется транзиентным, если вероятность когда-либо вернуться в него меньше $1$ .

В конечной неприводимой цепи все состояния рекуррентны. В бесконечных пространствах состояний возможны оба варианта. Например, случайное блуждание на $\mathbb{Z}$ рекуррентно, а на $\mathbb{Z}^3$ транзиентно.

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

Период состояния $i$ в дискретной цепи Маркова определяется как

$d(i)=\operatorname{gcd}\left\{\,n\geq 1:\; \mathbb{P}(X_n=i\mid X_0=i)>0\,\right\}.$

Если $d(i)=1$ , состояние называется апериодическим. Периодичность влияет на сходимость распределения $\mu_0P^n$ к стационарному распределению.

Эргодичность

Для конечной цепи Маркова часто используется следующий достаточный набор условий сходимости к стационарному распределению: неприводимость и апериодичность. В этом случае существует единственное стационарное распределение $\pi$ , и

$\mu_0P^n\to\pi,\qquad n\to\infty.$

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

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

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

$\pi_iP_{ij}=\pi_jP_{ji}.$

Из детального баланса следует стационарность распределения $\pi$ . Это условие часто используется при построении MCMC-алгоритмов, поскольку его обычно проще проверить, чем стационарность напрямую.

Сильное марковское свойство

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

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

Примеры

Случайное блуждание

Случайное блуждание — один из простейших примеров цепи Маркова. В одномерном случае процесс на $\mathbb{Z}$ может задаваться переходами

$\mathbb{P}(X_{n+1}=X_n+1)=p,\qquad \mathbb{P}(X_{n+1}=X_n-1)=1-p.$

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

Пуассоновский процесс

Пуассоновский процесс с интенсивностью $\lambda$ — марковский процесс в непрерывном времени на множестве $\mathbb{N}$ . Если $X_t$ — число событий к моменту $t$ , то переходы возможны только из $n$ в $n+1$ . Его генератор имеет вид

$q_{n,n+1}=\lambda,\qquad q_{nn}=-\lambda.$

Процесс рождения и гибели

Процесс рождения и гибели — непрерывновременная цепь Маркова на $\mathbb{N}$ , в которой переходы возможны только между соседними состояниями:

$n\to n+1,\qquad n\to n-1.$

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

Винеровский процесс

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

Марковские процессы в машинном обучении

Скрытые марковские модели

Скрытая марковская модель — это вероятностная модель, в которой скрытые состояния $Z_1,\ldots,Z_T$ образуют цепь Маркова, а наблюдения $X_1,\ldots,X_T$ зависят от текущих скрытых состояний. Типичная факторизация совместного распределения имеет вид

$p(z_{1:T},x_{1:T})=p(z_1)p(x_1\mid z_1)\prod_{t=2}^T p(z_t\mid z_{t-1})p(x_t\mid z_t).$

Основные алгоритмы для скрытых марковских моделей:

алгоритм Витерби — поиск наиболее вероятной последовательности скрытых состояний;
алгоритм прямого-обратного хода — вычисление апостериорных вероятностей скрытых состояний;
алгоритм Баума — Велша — частный случай EM-алгоритма для оценки параметров.

Марковские процессы принятия решений

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

$P(s'\mid s,a).$

Обычно MDP задаётся набором

$(S,A,P,R,\gamma),$

где $S$ — множество состояний, $A$ — множество действий, $P$ — переходная функция, $R$ — функция награды, $\gamma$ — коэффициент дисконтирования.

Если политика $\pi(a\mid s)$ фиксирована, то MDP индуцирует марковский процесс по состояниям. Теория MDP лежит в основе обучения с подкреплением, динамического программирования и уравнений Беллмана.

MCMC

Метод Монте-Карло по схеме марковских цепей строит цепь Маркова, стационарным распределением которой является заданное целевое распределение $\pi(x)$ . После начального участка траектории, называемого burn-in, состояния цепи используются как зависимая выборка из $\pi$ .

В алгоритме Метрополиса — Гастингса из текущего состояния $x$ предлагается новое состояние $y\sim q(y\mid x)$ , которое принимается с вероятностью

$\alpha(x,y)=\min\left{1,\frac{\pi(y)q(x\mid y)}{\pi(x)q(y\mid x)}\right}.$

Целевое распределение $\pi$ достаточно знать с точностью до нормировочной константы, что делает MCMC удобным инструментом байесовского вывода.

Марковские модели последовательностей

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

$p(x_{1:T})=p(x_1)\prod_{t=2}^T p(x_t\mid x_{t-1}).$

Модель порядка $k$ предполагает, что

$p(x_t\mid x_{t-1},\ldots,x_1)=p(x_t\mid x_{t-1},\ldots,x_{t-k}).$

Любой процесс порядка $k$ можно представить как процесс первого порядка, расширив состояние:

$Y_t=(X_{t-k+1},\ldots,X_t).$

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

Для конечной однородной цепи Маркова параметры матрицы переходов можно оценить по наблюдаемой траектории. Пусть $N_{ij}$ — число наблюдавшихся переходов из состояния $i$ в состояние $j$ . Тогда оценка максимального правдоподобия имеет вид

$\widehat P_{ij}=\frac{N_{ij}}{\sum_k N_{ik}}.$

Если некоторые переходы не наблюдались, применяют сглаживание. Например, при априорном распределении Дирихле можно использовать апостериорное среднее

$\widehat P_{ij}=\frac{N_{ij}+\alpha_{ij}}{\sum_k(N_{ik}+\alpha_{ik})}.$

В скрытых марковских моделях состояния не наблюдаются напрямую, поэтому параметры обычно оцениваются с помощью EM-алгоритма, вариационного вывода или MCMC.

Типичные замечания

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

См. также

Литература

Markov A. A. Extension of the law of large numbers to quantities, depending on each other. — 1906.
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, 2009; 2nd ed., 2017.
Puterman M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. — Wiley, 1994.
Sutton R. S., Barto A. G. Reinforcement Learning: An Introduction. — 2nd ed. — MIT Press, 2018.
Rabiner L. R. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition // Proceedings of the IEEE. — 1989.
Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. Equation of State Calculations by Fast Computing Machines // Journal of Chemical Physics. — 1953.
Hastings W. K. Monte Carlo Sampling Methods Using Markov Chains and Their Applications // Biometrika. — 1970.

Ссылки

Transition function — Encyclopedia of Mathematics.
Markov Chains I — MIT OpenCourseWare.
Markov Chains and Mixing Times — электронная версия книги Levin, Peres, Wilmer.
Reinforcement Learning: An Introduction — страница книги Sutton, Barto.
A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition — Rabiner, 1989.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81»

Категории: Теория вероятностей | Математическая статистика | Стохастические процессы | Машинное обучение | Обучение с подкреплением