Дискретные цепи Маркова: основы и свойства

Цепь Маркова, это последовательность случайных величин с дискретным временем и дискретным пространством состояний, обладающая свойством отсутствия памяти. Вероятность перехода в следующее состояние зависит исключительно от текущего состояния, а не от всей предшествующей истории системы. Именно эта особенность выделяет цепи Маркова среди более общих стохастических процессов и наделяет их важными аналитическими свойствами. Термин введён А. А. Марковым в работе 1906 года и стал фундаментом теории стохастических процессов с зависимостями ограниченной длины памяти[1].

Обозначим последовательность дискретных случайных величин как \(\{X_n\}_{n\geqslant 0}\). Цепь Маркова первого порядка удовлетворяет условию

\[
\mathbb {P} (X_{n+1}=i_{n+1} | X_n=i_n, X_{n-1}= i_{n-1}, ..., X_0 = i_0 ) =
\mathbb {P} (X_{n+1}= i_{n+1} | X_n = i_n).
\]

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

Для цепей Маркова более высокого порядка \( N > 1 \), вероятность наступления следующего состояния зависит от последних \( N \) состояний:

\[
\mathbb {P} (X_{n+1}= i_{n+1} | X_n = i_n, ..., X_0 = i_0 ) =
\mathbb {P}( X_{n+1}= i_{n+1} | X_n = i_n, X_{n-1} = i_{n-1}, ..., X_{n-N+1}= i_{n-N+1} ).
\]

При этом условное распределение опирается на текущее и \( N - 1 \) предыдущих состояний, что расширяет класс процессов по сравнению с простыми цепями первого порядка[1].

Пространство состояний и номера шагов

Множество всех возможных значений случайной величины \( X_n \) называется пространством состояний цепи. Номер шага процесса обозначается индексом \( n \), где каждый шаг соответствует одному дискретному моменту времени наблюдения или изменения состояния системы[1].

Матрица переходных вероятностей

Ключевым объектом для описания дискретной цепи Маркова является матрица переходных вероятностей \(P(n)\) с элементами \(P_{ij}(n) := \mathbb {P}( X_{n+1} = j | X_n = i ).\).

Эта матрица задаёт вероятности перехода из состояния \( i \) в состояние \( j \) на шаге \( n \). Для каждого фиксированного шага элементы строки матрицы суммируются в единицу:

\[
\sum_j P_{ij}(n) = 1,
\,\,\,\,\,\,
\forall n \in \mathbb{N}.
\]

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

Если при этом матрица не меняется со временем, то есть \(P_{ij}(n) = P_{ij}, \,\,\,\,\,\, \forall n,\) цепь называется однородной. Однородность упрощает анализ и вычисление распределений состояний через множество шагов[1].

Начальное распределение

Распределение вероятностей начального состояния цепи задаётся вектором \(\mathbf{p} = (p_1, p_2, ...)^T, \,\, p_i := \mathbb{P}(X_0 = i).\).

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

Эволюция распределения состояний

Распределение вероятностей по состояниям на шаге времени можно представить как строковый вектор \(c_t,\) где элемент \(c_{t,i}\) описывает вероятность нахождения процесса в состоянии \( i \) на момент времени \( t \). Известно, что переход к следующему распределению осуществляется умножением текущего вектора на матрицу переходов:

\[
c_{t+1} = c_t \times P.
\]

Благодаря ассоциативности умножения матриц можно выразить распределение через произвольное количество шагов:

\[
c_{t+s} = c_t \times P^s.
\]

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

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

Структура состояний может обладать сложными свойствами периодичности. Если существует период \(d > 1,\) то состояние разделяется на циклические классы, непересекающиеся подмножества состояний, между которыми процесс переходит последовательно с периодом \( d \)[5]. В противном случае цепь называется апериодической.

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

Для заданных состояний обозначим за \(N_{i,j}\) множество чисел шагов, за которые можно попасть из состояния \( i \) в состояние \( j \), а за \(d_i\) наибольший общий делитель элементов множества \(N_{i,i},\) который определяет периодичность возвращения в состояние \( i \)[5].

Поглощающие состояния

Поглощающим называется такое состояние, из которого невозможно выйти, вероятность остаться там равна единице. Обозначим массив переходов как `transition`, где `transition[i][2]` — вероятность перехода из состояния `transition[i][0]` в состояние `transition[i][1]`. Если для некоторого индекса `j` состояние `j` является поглощающим, то `transition[j][2] = 1`. Это ключевой признак устойчивости некоторых состояний и используется для анализа предельного поведения системы[5].

Исторический контекст и практическое применение

Теория дискретных цепей Маркова была развита начиная с работ А.А. Маркова с начала XX века. В частности, исследование Романовского «Дискретные цепи Маркова» (1949 год) помогло Госплану составить более точные прогнозные значения промышленного развития посредством применения марковских моделей к экономическим задачам[2]. С тех пор методы анализа марковских процессов стали стандартным инструментом для моделирования систем с памятью конечного объёма, от биологических систем до финансовых рынков и технических систем управления.

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

Дискретные цепи Маркова обеспечивают удобный формализм для работы с процессами, где будущее зависит лишь от ограниченного количества прошлых событий. Их теория содержит чёткие критерии для классификации поведения системы: однородность или неоднородность во времени, наличие периодичности или эргодичности, существование поглощающих состояний и др., что позволяет глубоко анализировать динамические свойства широкого класса стохастических процессов[3][4][5].