Це́пь Ма́ркова — последовательность случайных событий с конечным или счётным числом исходов, где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем событии[1]. Характеризуется тем свойством, что, говоря нестрого, при текущем настоящем состоянии системы, её будущее состояние не зависит от прошлого. Названа в честь А. А. Маркова (старшего), который впервые ввёл это понятие в работе 1906 года.[2]
Цепь Маркова с дискретным временем
Определение
Последовательность дискретныхслучайных величин называется простой цепью Маркова (с дискретным временем), если
.
Таким образом, в простейшем случае условное распределение последующего состояния цепи Маркова зависит только от текущего состояния и не зависит от всех предыдущих состояний (в отличие от цепей Маркова высших порядков).
Область значений случайных величин называется простра́нством состоя́ний цепи, а номер — номером шага.
Семейство дискретных случайных величин называется цепью Маркова (с непрерывным временем), если
.
Цепь Маркова с непрерывным временем называется однородной, если
.
Матрица переходных функций и уравнение Колмогорова — Чепмена
Аналогично случаю дискретного времени, конечномерные распределения однородной цепи Маркова с непрерывным временем полностью определены начальным распределением
и ма́трицей перехо́дных фу́нкций (переходных вероятностей)
Граф переходов, связность и эргодические цепи Маркова
Для цепи Маркова с непрерывным временем строится ориентированный граф переходов (кратко — граф переходов) по следующим правилам:
Множество вершин графа совпадает со множеством состояний цепи.
Вершины соединяются ориентированным ребром , если (то есть интенсивность потока из -го состояния в -е положительна).
Топологические свойства графа переходов связаны со спектральными свойствами матрицы . В частности, для конечных цепей Маркова верны следующие теоремы:
Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими):
А. Для любых двух различных вершин графа переходов найдется такая вершина графа («общий сток»), что существуют ориентированные пути от вершины к вершине и от вершины к вершине . Замечание: возможен случай или ; в этом случае тривиальный (пустой) путь от к или от к также считается ориентированным путём.
Б. Нулевое собственное число матрицы невырождено.
В. При матрица стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими):
А. Граф переходов цепи ориентированно связен.
Б. Нулевое собственное число матрицы невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).
В. Для некоторого матрица строго положительна (то есть для всех ).
Г. Для всех матрица строго положительна.
Д. При матрица стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
Примеры
Рассмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — , в случае (b) отличны от нуля только , а в случае (c) — .
Остальные элементы определяются свойствами матрицы (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид:
Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина англ.Master equation. Для вектора-строки распределения вероятностей основное кинетическое уравнение имеет вид:
и совпадает, по существу, с прямым уравнением Колмогорова. В физической литературе чаще используют векторы-столбцы вероятностей и записывают основное кинетическое уравнение в виде, который явно использует закон сохранения полной вероятности:
где
Если для основного кинетического уравнения существует положительное равновесие , то его можно записать в форме
Функции Ляпунова для основного кинетического уравнения
Для основного кинетического уравнения существует богатое семейство выпуклыхфункций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть — выпуклая функция одного переменного. Для любого положительного распределения вероятностей () определим функцию Моримото:
.
Производная по времени, если удовлетворяет основному кинетическому уравнению, есть
.
Последнее неравенство справедливо из-за выпуклости .
Примеры функций Моримото
, ;
эта функция — расстояние от текущего распределения вероятностей до равновесного в -норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.)
эта функция — аналог свободной энергии для энтропии Бурга, широко используемой в обработке сигналов:
, ;
это квадратичное приближение для (минус) энтропии Кульбака вблизи точки равновесия. С точностью до постоянного во времени слагаемого эта функция совпадает с (минус) энтропией Фишера, которую даёт следующий выбор,
это один из аналогов свободной энергии для энтропии Тсаллиса[англ.].
служит основой для статистической физики неэкстенсивных величин. При она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.
Одной из первых научных дисциплин, в которой цепи Маркова нашли практическое применение, стала лингвистика (в частности текстология). Сам Марков для иллюстрации своих результатов исследовал зависимость в чередовании гласных и согласных в первых главах «Евгения Онегина» и «Детских годов Багрова-внука»[3].
Gagniuc, Paul A.Markov Chains: From Theory to Implementation and Experimentation(англ.).— USA, NJ: John Wiley & Sons, 2017.— P.2—8.— ISBN 978-1-119-38755-8.
Кельберт М. Я., Сухов Ю. М.Вероятность и статистика в примерах и задачах. Т. ІІ: Марковские цепи как отправная точка теории случайных процессов и их приложения.— М.: МЦНМО, 2010.— 295с.— ISBN 978-5-94057-252-7.
Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.