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

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

(Различия между версиями)

Текущая версия

Статья написана с использованием 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 Ссылки

Определение

Пусть ${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.$

Цепь Маркова

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

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

Подробно свойства цепей Маркова, включая классификацию состояний, периодичность, стационарные распределения и сходимость, рассматриваются в отдельной статье Цепь Маркова.

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

Если множество моментов времени непрерывно, например $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.$

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

Долгосрочное поведение

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

Для конечной неприводимой и апериодической цепи существует единственное стационарное распределение $\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.$

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

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

Пуассоновский процесс с интенсивностью $\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},x_{1})=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).$

Основные алгоритмы для скрытых марковских моделей: алгоритм Витерби, алгоритм прямого-обратного хода и алгоритм Баума — Велша.

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

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

$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})=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://www.recognition.su/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»

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