Марковская цепь

Марковская цепь — это математическая модель случайного процесса, в котором будущее состояние системы зависит только от её текущего состояния и не зависит от того, как система пришла в это состояние (свойство отсутствия последействия, или марковское свойство). Формально, марковская цепь представляет собой последовательность случайных величин (состояний), для которой условное распределение вероятностей следующего состояния при известном текущем не зависит от всех предыдущих состояний. Марковские цепи являются фундаментальным понятием теории вероятностей и находят широкое применение в физике, биологии, экономике, компьютерных науках, лингвистике и других областях.

История

Основы теории марковских цепей были заложены русским математиком Андреем Андреевичем Марковым (старшим). В 1906 году он опубликовал работу «Распространение закона больших чисел на величины, зависящие друг от друга», в которой впервые исследовал последовательности случайных событий, связанных в цепь. Марков изучал чередование гласных и согласных в поэме Пушкина «Евгений Онегин», стремясь построить вероятностную модель, где вероятность появления следующей буквы зависит только от предыдущей. Эта работа стала отправной точкой для развития цепей Маркова.

В 1913 году Марков опубликовал статью «Пример статистического исследования текста „Евгения Онегина“», где применил свою модель к анализу литературного произведения. Позднее, в 1920-х годах, советский математик Александр Яковлевич Хинчин и другие учёные развили теорию марковских процессов, обобщив её на непрерывное время. В 1931 году Андрей Николаевич Колмогоров опубликовал фундаментальную работу «Об аналитических методах в теории вероятностей», в которой заложил основы теории марковских процессов с непрерывным временем. В середине XX века, с развитием вычислительной техники, марковские цепи стали активно применяться в моделировании случайных процессов, машинном обучении и обработке сигналов.

Определение и основные понятия

Марковская цепь задаётся набором состояний (конечным или счётным) и матрицей переходных вероятностей. Состояния обозначаются как \( S = \{s_1, s_2, \dots, s_n\} \). Матрица переходных вероятностей \( P \) размера \( n \times n \) содержит элементы \( p_{ij} \), где \( p_{ij} = P(X_{t+1} = s_j \mid X_t = s_i) \) — вероятность перехода из состояния \( i \) в состояние \( j \) за один шаг. Сумма вероятностей по строке матрицы равна единице: \( \sum_{j} p_{ij} = 1 \) для каждого \( i \).

Марковское свойство (отсутствие последействия) формально записывается как: \[ P(X_{t+1} = s_j \mid X_t = s_i, X_{t-1} = s_k, \dots, X_0 = s_m) = P(X_{t+1} = s_j \mid X_t = s_i). \]

Цепь может быть однородной (стационарной), если переходные вероятности не зависят от времени \( t \), и неоднородной, если они меняются со временем.

Классификация марковских цепей

Марковские цепи классифицируются по нескольким признакам.

По типу состояний

• Возвратные состояния: вероятность когда-либо вернуться в это состояние равна 1. Если цепь начинает движение из возвратного состояния, она будет возвращаться в него бесконечное число раз.
• Невозвратные состояния: вероятность возврата меньше 1. Цепь может покинуть такое состояние навсегда.
• Поглощающие состояния: состояние, из которого невозможен выход (\( p_{ii} = 1 \)). Попав в него, цепь остаётся в нём навсегда.

По структуре цепи

• Неприводимые цепи: из любого состояния можно перейти в любое другое (за конечное число шагов).
• Периодические и апериодические цепи: если для некоторого состояния \( i \) существует наибольший общий делитель \( d \) длин всех циклов (путей возврата), то состояние называется периодическим с периодом \( d \). Если \( d = 1 \), состояние апериодическое. Цепь называется апериодической, если все её состояния апериодические.

По числу состояний

• Конечные марковские цепи: число состояний конечно.
• Счётные марковские цепи: число состояний счётно (бесконечно, но дискретно).

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

Для эргодических (неприводимых, апериодических и возвратных) марковских цепей существует единственное стационарное распределение \( \pi = (\pi_1, \pi_2, \dots, \pi_n) \), удовлетворяющее уравнению: \[ \pi = \pi P, \] где \( \pi_i \) — доля времени, которую цепь проводит в состоянии \( i \) при бесконечно длительном наблюдении. Стационарное распределение не зависит от начального состояния цепи.

Примеры и применение

Пример 1: Погода

Простейшая модель погоды: два состояния — «солнечно» (С) и «дождливо» (Д). Матрица переходов может быть, например, такой: \[ P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix}. \] Это означает, что после солнечного дня с вероятностью 0.9 будет снова солнечно, а с вероятностью 0.1 — дождливо; после дождливого дня с вероятностью 0.5 будет солнечно, с вероятностью 0.5 — снова дождливо. Стационарное распределение для такой цепи можно найти, решив систему уравнений: \( \pi_1 = 0.9\pi_1 + 0.5\pi_2 \), \( \pi_2 = 0.1\pi_1 + 0.5\pi_2 \), \( \pi_1 + \pi_2 = 1 \). Решение: \( \pi_1 = 5/6 \approx 0.833 \), \( \pi_2 = 1/6 \approx 0.167 \).

Пример 2: Случайное блуждание

Классическая модель — случайное блуждание по целым числам. Состояния — целые числа, из каждого состояния \( i \) можно перейти в \( i+1 \) с вероятностью \( p \) и в \( i-1 \) с вероятностью \( q = 1-p \). Такая цепь является счётной и может быть возвратной или невозвратной в зависимости от \( p \) и \( q \).

Применение в компьютерных науках

• Алгоритмы сэмплирования (например, метод Монте-Карло на основе цепей Маркова, MCMC) используются для приближённого вычисления сложных распределений.
• Моделирование текстов (генерация текста с помощью марковских цепей) — на основе статистики переходов между словами или символами.
• Распознавание речи и обработка естественного языка — скрытые марковские модели (HMM) применяются для анализа последовательностей, например, для распознавания фонем или частей речи.
• Анализ веб-графов — алгоритм PageRank от Google основан на модели случайного блуждания по ссылкам, которая является марковской цепью.

Применение в физике и биологии

• Моделирование диффузии и броуновского движения.
• Эпидемиологические модели (например, модель SIR, где состояния — восприимчивые, инфицированные, выздоровевшие).
• Генетика — модели эволюции последовательностей ДНК (модели Jukes-Cantor, Kimura).

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

Скрытая марковская модель — это расширение марковской цепи, в котором наблюдаемые события (выходные сигналы) зависят от ненаблюдаемых (скрытых) состояний. Формально, HMM задаётся:

• множеством скрытых состояний \( S \);
• множеством наблюдаемых символов \( V \);
• матрицей переходных вероятностей \( A \);
• матрицей эмиссионных вероятностей \( B \) (вероятность наблюдения символа \( v_k \) в состоянии \( s_i \));
• начальным распределением \( \pi \).

HMM широко применяются в распознавании речи, биоинформатике (поиск генов), анализе временных рядов и машинном обучении.

Интересные факты

• Андрей Марков использовал свою модель для анализа чередования букв в поэме «Евгений Онегин», чтобы опровергнуть утверждение о независимости событий в статистике.
• Алгоритм PageRank, разработанный Ларри Пейджем и Сергеем Брином, моделирует поведение «случайного серфера», который с вероятностью 0.85 переходит по ссылкам на веб-страницах и с вероятностью 0.15 переходит на случайную страницу. Это классическая марковская цепь.
• Марковские цепи лежат в основе многих современных генеративных моделей, включая модели для создания музыки и изображений.

Критика и ограничения

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

Источники

• Марков А. А. «Пример статистического исследования текста „Евгения Онегина“», 1913.
• Колмогоров А. Н. «Об аналитических методах в теории вероятностей», 1931.
• Хинчин А. Я. «Основные понятия теории вероятностей», 1928.
• Norris J. R. «Markov Chains», Cambridge University Press, 1997.
• Rabiner L. R. «A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition», 1989.